Attacking the Market Split Problem with Lattice Point Enumeration
Author: Wassermann A.
Source: Journal of Combinatorial Optimization, Volume 6, Number 1, March 2002 , pp. 5-16(12)
The market split problem was proposed by Cornuéjols and Dawande as benchmark problem for algorithms solving linear systems with 0/1 variables. Here, we present an algorithm for the more general problem A · x = b with arbitrary lower and upper bound on the variables. The algorithm consists of exhaustive enumeration of all points of a suitable lattice which are contained in a given polyhedron. We present results for the feasibility version as well as for the integer programming version of the market split problem which indicate that the algorithm outperforms the previously published approaches to this problems considerably.
Document Type: Regular paper
Publication date: 2002-03-01