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         23-May-2005 10:34     4k  
 markshare_3_0.mps.gz    23-May-2005 10:34     1k  MPS format instance
 markshare_3_1.mps.gz    23-May-2005 10:34     1k  MPS format instance
 markshare_3_2.mps.gz    23-May-2005 10:34     1k  MPS format instance
 markshare_3_3.mps.gz    23-May-2005 10:34     1k  MPS format instance
 markshare_3_4.mps.gz    23-May-2005 10:34     1k  MPS format instance
 markshare_3_5.mps.gz    23-May-2005 10:34     1k  MPS format instance
 markshare_4_0.mps.gz    23-May-2005 10:34     1k  MPS format instance
 markshare_4_1.mps.gz    23-May-2005 10:34     1k  MPS format instance
 markshare_4_2.mps.gz    23-May-2005 10:34     1k  MPS format instance
 markshare_4_3.mps.gz    23-May-2005 10:34     1k  MPS format instance
 markshare_4_4.mps.gz    23-May-2005 10:34     1k  MPS format instance
 markshare_4_5.mps.gz    23-May-2005 10:34     1k  MPS format instance
 markshare_5_0.mps.gz    23-May-2005 10:34     1k  MPS format instance
 markshare_5_1.mps.gz    23-May-2005 10:34     1k  MPS format instance
 markshare_5_2.mps.gz    23-May-2005 10:34     1k  MPS format instance
 markshare_5_3.mps.gz    23-May-2005 10:34     1k  MPS format instance
 markshare_5_4.mps.gz    23-May-2005 10:34     1k  MPS format instance
 markshare_6_0.mps.gz    23-May-2005 10:34     1k  MPS format instance
 markshare_6_1.mps.gz    23-May-2005 10:34     1k  MPS format instance
 markshare_6_2.mps.gz    23-May-2005 10:34     1k  MPS format instance
 markshare_6_3.mps.gz    23-May-2005 10:34     1k  MPS format instance
 markshare_6_4.mps.gz    23-May-2005 10:34     1k  MPS format instance