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


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


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