Journal
SIAM JOURNAL ON OPTIMIZATION
Volume 16, Issue 3, Pages 726-750Publisher
SIAM PUBLICATIONS
DOI: 10.1137/040609574
Keywords
integer programming; lift-and-project relaxations; semidefinite programming; augmented Lagrangian
Categories
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available