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)

Publisher: Springer

Buy & download fulltext article:

Price: $47.00 plus tax (Refund Policy)

Abstract:

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.

Keywords: market split problem; Diophantine linear systems; lattice point enumeration; lattice basis reduction; integer linear programming; subset sum problem

Language: English

Document Type: Regular paper

Affiliations: 1: Universität Bayreuth, Mathematisches Institut, D-95440, Bayreuth, Germany. alfred.wassermann@uni-bayreuth.de

Publication date: 2002-03-01