Semidefinite Relaxations and Lagrangian Duality with Application to Combinatorial Optimization
Résumé
We show that it is fruitful to dualize the integrality constraints in a combinatorial optimization problem. First, this reproduces the known SDP relaxations of the max-cut and max-stable problems. Then we apply the approach to general combinatorial problems. We show that the resulting duality gap is smaller than with the classical Lagrangian relaxation; we also show that linear constraints need a special treatment.