CRPC-TR99787-S						June 1999

Title: Market Split and Basis Reduction: Towards a Solution of the
CornuŽlos-Dawande Instances

Authors: K. Aardal, R. E. Bixby, C. A. J. Hurkens, A. K. Lenstra, and J.
W. Smeltink 

Submitted June 1999

Abstract:
	At the IPCO VI conference CornuŽlos and Dawande proposed a set of
0-1 linear programming instances that proved to be very hard to solve by
traditional methods, and in particular by linear programming based
branch-and-bound.  They offered these market-split instances as a
challenge to the integer programming 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 algorithm of Aardal, Hurkens, and Lenstra
(1998) based on lattice basis reduction.  This algorithm is not restricted
to deal with market split instances only but is a general method for
solving systems of linear diophantine equations with bounds on the
variables.
	We show computational results from solving both feasibility and
optimization versions of the market split instances with up to 7 equations
and 60 variables, and discuss various branching strategies and their
effect on the number of enumerated nodes.  To our knowledge, the largest
feasibility and optimization instances solved before had 6 equations and
50 variables, and 4 equations and 30 variables respectively.
	We also present a probabilistic analysis describing how to compute
the probability of generating infeasible market split instances.  By
generating instances the way prescribed by CornuŽlos and Dawande, one
obtains relatively many feasible instances for sizes larger than 5
equations and 40 variables.

------------------------------------------------------------------------------
Karen Aardal
aardal@cs.uu.nl
Department of Computer Science
Utrecht University

R. E. Bixby
bixby@caam.rice.edu
Department of Computational and Applied Mathematics
Rice University

C. A. J. Hurkens
wscor@win.tue.nl
Department of Mathematics and Computing Science
Eindhoven University of Technology

A. K. Lenstra
arjen.lenstra@citicorp.com
Emerging Technology, Citibank N. A.

J. W. Smeltink
job@cs.uu.nl
Department of Computer Science
Utrecht University