-

 

 

 




Optimization Online





 

Block-diagonal semidefinite programming hierarchies for 0/1 programming

N. Gvozdenovic (n.gvozdenovic***at***cwi.nl)
M. Laurent (monique***at***cwi.nl)
F. Vallentin (f.vallentin***at***cwi.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: 08/19/2008

Modify/Update this entry


  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository

 

Submit
Update
Policies
Coordinator's Board
Classification Scheme
Credits
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society