Block-diagonal semidefinite programming hierarchies for 0/1 programming
Operations Research Letters , Volume 37 p. 27- 31
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|
|MSC||Semidefinite programming (msc 90C22), Combinatorial optimization (msc 90C27)|
|THEME||Logistics (theme 3)|
|Journal||Operations Research Letters|
|Project||Semidefinite programming and combinatorial optimization|
Gvozdenovic, N, Laurent, M, & Vallentin, F. (2009). Block-diagonal semidefinite programming hierarchies for 0/1 programming. Operations Research Letters, 37, 27–31.