Markshare Instances

The markshare__.mps are IP instances of the form $Ax = b, x_i \in \{0,1\}$ in MPS format, where - there are m inequalities - and $n = 10 (m - 1)$ variables. - Each integer coefficient $a_{ij}$ is randomly picket from the range between 0 and D-1, - the rhs is defined by $b_i = \lfloor \tfrac{1}{2} \sum_{j=1}^n a_{ij} \rfloor$, - and the objective is 0. - 'seed' is used to initialize the (pseudo) random number generator.

Related to this are optimization versions (see Cornuéjols and Dawande and the markshare instances in MIPLIB 2003).

The resulting (feasibility and optimization) instances are considered hard. Currently, the largest instances that can be solved have m = 7 inequalities (see Aardal et al. below).

Note that with larger m (e.g. $m > 7$) the probability to obtain a feasible instance increases (one has to take slightly fewer variables than $10 (m - 1)$), see

K. Aardal, R.E. Bixby, C.A.J. Hurkens, A.K. Lenstra, and J.W. Smeltink "Market split and basis reduction: towards a solution of the Cornuéjols-Dawande instances" INFORMS J. Comput. 12, No. 3, pp. 192-202, 2000.

Thanks to Marc Pfetsch for contributing the instances and the instance generator implemented in C++.

 Name                    Last modified      Size  Description
 gen_markshare.C         2013-03-11 10:03  4.1K  
 markshare_3_0.mps.gz    2005-05-23 10:34  426   MPS format instance
 markshare_3_1.mps.gz    2005-05-23 10:34  424   MPS format instance
 markshare_3_2.mps.gz    2005-05-23 10:34  424   MPS format instance
 markshare_3_3.mps.gz    2005-05-23 10:34  421   MPS format instance
 markshare_3_4.mps.gz    2005-05-23 10:34  424   MPS format instance
 markshare_3_5.mps.gz    2005-05-23 10:34  418   MPS format instance
 markshare_4_0.mps.gz    2005-05-23 10:34  642   MPS format instance
 markshare_4_1.mps.gz    2005-05-23 10:34  631   MPS format instance
 markshare_4_2.mps.gz    2005-05-23 10:34  633   MPS format instance
 markshare_4_3.mps.gz    2005-05-23 10:34  632   MPS format instance
 markshare_4_4.mps.gz    2005-05-23 10:34  630   MPS format instance
 markshare_4_5.mps.gz    2005-05-23 10:34  635   MPS format instance
 markshare_5_0.mps.gz    2005-05-23 10:34  958   MPS format instance
 markshare_5_1.mps.gz    2005-05-23 10:34  955   MPS format instance
 markshare_5_2.mps.gz    2005-05-23 10:34  948   MPS format instance
 markshare_5_3.mps.gz    2005-05-23 10:34  953   MPS format instance
 markshare_5_4.mps.gz    2005-05-23 10:34  955   MPS format instance
 markshare_6_0.mps.gz    2005-05-23 10:34  1.3K  MPS format instance
 markshare_6_1.mps.gz    2005-05-23 10:34  1.2K  MPS format instance
 markshare_6_2.mps.gz    2005-05-23 10:34  1.2K  MPS format instance
 markshare_6_3.mps.gz    2005-05-23 10:34  1.3K  MPS format instance
 markshare_6_4.mps.gz    2005-05-23 10:34  1.3K  MPS format instance