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++.

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