Solving Lift-and-Project Relaxations of Binary Integer Programs

**Joint work with D. Vandenbussche, U. of Illinois

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 much more
quickly than state-of-the-art linear and semidefinite solvers.