Solving Lift-and-Project Relaxations of Binary Integer Programs

Samuel Burer (samuel-bureruiowa.edu)
Dieter Vandenbussche (dietervuiuc.edu)

Abstract: 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.

Keywords: integer programming, lift-and-project, relaxations, semidefinite programming, augmented Lagrangian

Category 1: Integer Programming (0-1 Programming )

Category 2: Linear, Cone and Semidefinite Programming

Citation: Department of Mechanical and Industrial Engineering, University of Illinois Urbana-Champaign, June 2004

Download: [PDF]

Entry Submitted: 06/07/2004
Entry Accepted: 06/07/2004
Entry Last Modified: 06/07/2004

Modify/Update this entry