Market split and basis reduction: Towards a solution of the Cornuéjols-Dawande instances

Karen Aardal, Robert E Bixby, Cor Hurkens, Arjen K Lenstra, Job W Smeltink

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review

14 Citations (Scopus)

Abstract

At the IPCO VI conference Cornuéjols 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 (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 nodes enumerated. To our knowledge, the largest feasibility and optimization instances solved before have 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. The formula used by Cornuéjols and Dawande tends to produce relatively many feasible instances for sizes larger than 5 equations and 40 variables.
Original languageEnglish
Title of host publicationInteger Programming and Combinatorial Optimization: 7th International IPCO Conference
PublisherSpringer
Pages1-16
Number of pages16
ISBN (Electronic)978-3-540-48777-7
ISBN (Print)978-3-540-66019-4
DOIs
Publication statusPublished - 1999
Externally publishedYes

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume1610

Keywords

  • Diophantine Equation
  • Feasibility Problem
  • Probability Generate Function
  • Basis Reduction
  • Optimization Version

Fingerprint Dive into the research topics of 'Market split and basis reduction: Towards a solution of the Cornuéjols-Dawande instances'. Together they form a unique fingerprint.

Cite this