Solving Lift-and-Project Relaxations of Binary Integer Programs
Sam Burer, University of Iowa
(joint work with Dieter Vandenbussche)
We propose a method for optimizing the lift-and-project
relaxations of binary integer programs introduced by Lov\'asz and
Schrijver. In particular, we study both linear and semidefinite
relaxations. The key idea is a restructuring of the relaxations,
which isolates the complicating constraints and allows for a
Lagrangian approach. We detail an enhanced subgradient method and
discuss its efficient implementation. Computational results
illustrate that our algorithm produces tight bounds more quickly
than state-of-the-art linear and semidefinite solvers.
Chemnitz Workshop
Last modified: Fri Aug 20 15:18:05 CEST 2004