Cuts for mixed 0-1 conic programs
In this we talk we survey techniques for generating valid convex
constraints for mixed 0-1 conic programs. We show that many of the
techniques developed for generating linear cuts for mixed 0-1 linear
programs, such as the Gomory cuts, the lift-and-project cuts, and cuts
from other hierarchies of tighter relaxations, extend in a straightforward
manner to mixed 0-1 conic programs. We also show that simple extensions of
these techniques lead to methods for generating convex quadratic
cuts. Gomory cuts for mixed 0-1 conic programs have interesting
implications for comparing the semidefinite programming and the linear
programming relaxations of combinatorial optimization problems, e.g. we
show that all the subtour elimination inequalities for the traveling
salesman problem are rank-1 Gomory cuts with respect to a single
semidefinite constraint. We also include results from our preliminary
computational experiments with these cuts.
Chemnitz Workshop
Last modified: Wed Oct 13 11:19:49 CEST 2004