Block-diagonal semidefinite programming hierarchies for 0/1 programming

N. Gvozdenovic(n.gvozdenoviccwi.nl)
M. Laurent(moniquecwi.nl)
F. Vallentin(f.vallentincwi.nl)

Abstract: Lovasz and Schrijver, and later Lasserre, proposed hierarchies of semidefinite programming relaxations for general 0/1 linear programming problems. In this paper these two constructions are revisited and a new, block-diagonal hierarchy is proposed. It has the advantage of being computationally less costly while being at least as strong as the Lovasz-Schrijver hierarchy. It is applied to the stable set problem and experimental results for Paley graphs are reported.

Keywords: 0/1 linear programming, semidefinite programming, stable sets, Payley graphs

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 2: Combinatorial Optimization

Citation:

Download: [PDF]

Entry Submitted: 12/18/2007
Entry Accepted: 12/18/2007
Entry Last Modified: 12/18/2007

Modify/Update this entry