Market split and basis reduction: Towards a solution of the Cornuejols-Dawande instances

At the IPCO VI conference Cornuejols and Dawande proposed a set of 0-1 line ar programming instances that proved to be very hard to solve by traditiona l methods, and in particular by linear programming-based branch-and-bound. They offered these market split instances as a challenge to the integer pro gramming community. The market split problem can be formulated as a system of linear diophantine equations in 0-1 variables. In our study we use the a lgorithm of Aardal, Hurkens, and Lenstra (1998) based on lattice basis redu ction. This algorithm is not restricted to deal with market split instances only but is a general method for solving systems of linear diophantine equ ations with bounds on the variables. We show computational results from sol ving both feasibility and optimization versions of the market split instanc es with up to 7 equations and 60 variables and discuss various branching st rategies and their effect on the number of enumerated nodes. To our knowled ge, the largest feasibility and optimization instances solved before had 6 equations end 50 variables, and 4 equations and 30 variables, respectively. We also present a probabilistic analysis describing how to compute the pro bability of generating infeasible market split instances. By generating ins tances the way prescribed by Cornuejols and Dawande, one obtains relatively many feasible instances for sizes larger than 5 equations and 40 variables .