Solving the seymour problem
Michael C. Ferris · 2001
Optimization problems are at the heart of much of operations research and can vary substantially both in complexity and size. In many problems, the sheer size of the instance makes it very difficult to solve due to time or space limitations. In others, the complexity of the problem (nonlinearities, nonconvexities, or discreteness) can make it difficult or impossible to solve to optimality, even for reasonable sized instances. This note addresses an instance of the latter type of problem, arising as a mixed integer program (MIP) involving discrete variables and linear functions. Hard problems in MIPLIB The MIPLIB library of mixed integer programs was created in 1992 ([4]) and most recently updated in 1998 ([5]). Several problems in the library gained some notoriety, for being among the toughest. Some of these are: • The danoint and dano3mip problems that arise from network design; the latter of these is unsolved to this date. • The markshare problems, that were created with particular malice to challenge branchand-bound, and cutting plane algorithms. • The seymour problem: a relatively small setcovering problem with a fascinating origin, and of remarkable difficulty. A group of researchers, consisting of the authors, of Sebastian Ceria at Columbia University, and Jeff Linderoth at Argonne National Laboratory has recently succeeded in solving the seymour problem. In this article, we describe why we found this problem so alluring, what experiments we have done, and eventually, what techniques led us to its solution. Background on seymour The seymour problem is a setcovering problem; i.e. a problem of the form where e denotes a vector of all ones of appropriate dimension, and A is a matrix of zeros and ones. The number of rows in A is 4944 and the number of columns is 1372. The instance was posed by Paul Seymour, as a byproduct of a new proof of the Four Color