A Class of Hard Small 0—1 Programs

In this session, I will show a class of binary linear programming problems that poses major difficulties to branch-and-cut solvers. We will also discuss the developments induced by this observation, as market split instances have proven helpful both for the MIP theory (suggesting a study of lattice-based approaches) and for dynamic programming techniques.

A Class of Hard Small 0—1 Programs

Gérard Cornuéjols, and Milind Dawande

In Integer Programming and Combinatorial Optimization, Jan 1998

Abs HTML

In this paper, we consider a class of 0–1 programs which, although innocent looking, is a challenge for existing solution methods. Solving even small instances from this class is extremely difficult for conventional branch-and-bound or branch-and-cut algorithms. We also experimented with basis reduction algorithms and with dynamic pro- gramming without much success. The paper then examines the perfor- mance of two other methods: a group relaxation for 0,1 programs, and a sorting-based procedure following an idea of Wolsey. Although the re- sults with these two methods are somewhat better than with the other four when it comes to checking feasibility, we offer this class of small 0,1 programs as a challenge to the research community. As of yet, instances from this class with as few as seven constraints and sixty 0–1 variables are unsolved.
Michael A. Trick

Annals of Operations Research, Jan 2003

HTML

Relevant papers