Block-diagonal semidefinite programming hierarchies for 0/1 programming

Simple item page
dc.creatorGvozdenovic, N.
dc.creatorLaurent, M.
dc.creatorVallentin, F.
dc.date2007-12-19
dc.date2008-08-19
dc.date.accessioned2026-07-07T12:23:26Z
dc.date.available2026-07-07T12:23:26Z
dc.descriptionLovasz 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 two new, block-diagonal hierarchies are proposed. They have the advantage of being computationally less costly while being at least as strong as the Lovasz-Schrijver hierarchy. Our construction is applied to the stable set problem and experimental results for Paley graphs are reported.
dc.description11 pages, (v2) revision based on suggestions by referee, computation of N+(TH(P_q)) included in Table 2
dc.identifierhttps://arxiv.org/abs/0712.3079
dc.identifierhttp://arxiv.org/abs/0712.3079
dc.identifierOper. Res. Lett., 37 (2009), 27-31
dc.identifierdoi:10.1016/j.orl.2008.10.003
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/213987
dc.subjectOptimization and Control
dc.subject90C22; 90C27
dc.titleBlock-diagonal semidefinite programming hierarchies for 0/1 programming
dc.typetext

Files

Collections

arXiv