Block-diagonal semidefinite programming hierarchies for 0/1 programming |
| |
| Authors: | Neboj&scaron a Gvozdenovi?,Frank Vallentin |
| |
| Affiliation: | a The Faculty of Economics, University of Novi Sad, Segedinski put 9-11, 24000 Subotica, Serbia
b Centrum voor Wiskunde en Informatica (CWI), Kruislaan 413, 1098 SJ Amsterdam, The Netherlands |
| |
| Abstract: | Lovász and Schrijver, and later Lasserre, proposed hierarchies of semidefinite programming relaxations for 0/1 linear programming problems. We revisit these two constructions and propose two new, block-diagonal hierarchies, which are at least as strong as the Lovász-Schrijver hierarchy, but less costly to compute. We report experimental results for the stable set problem of Paley graphs. |
| |
| Keywords: | 0/1 linear programming Semidefinite programming Stable sets Payley graphs |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
