Journal article
Solving Lift-and-Project Relaxations of Binary Integer Programs
SIAM journal on optimization, Vol.16(3), pp.726-750
01/01/2006
DOI: 10.1137/040609574
Abstract
We propose a method for optimizing the lift-and-project relaxations of binary integer programs introduced by Lovasz 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.
Details
- Title: Subtitle
- Solving Lift-and-Project Relaxations of Binary Integer Programs
- Creators
- Samuel Burer - University of IowaDieter Vandenbussche - University of Illinois Urbana-Champaign
- Resource Type
- Journal article
- Publication Details
- SIAM journal on optimization, Vol.16(3), pp.726-750
- Publisher
- Society for Industrial and Applied Mathematics
- DOI
- 10.1137/040609574
- ISSN
- 1052-6234
- eISSN
- 1095-7189
- Language
- English
- Date published
- 01/01/2006
- Academic Unit
- Business Analytics
- Record Identifier
- 9984380535602771
Metrics
12 Record Views