Solving lift-and-project relaxations of binary integer programs

被引:46
作者
Burer, S [1 ]
Vandenbussche, D
机构
[1] Univ Iowa, Dept Management Sci, Iowa City, IA 52242 USA
[2] Univ Illinois, Dept Mech & Ind Engn, Urbana, IL 61801 USA
关键词
integer programming; lift-and-project relaxations; semidefinite programming; augmented Lagrangian;
D O I
10.1137/040609574
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
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.
引用
收藏
页码:726 / 750
页数:25
相关论文
共 38 条