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