Block-diagonal semidefinite programming hierarchies for 0/1 programming

DOI10.1016/j.orl.2008.10.003zbMath1154.90606arXiv0712.3079OpenAlexW2133943301MaRDI QIDQ1002080

Monique Laurent, Nebojša Gvozdenović, Frank Vallentin

Publication date: 23 February 2009

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0712.3079

zbMATH Keywords

semidefinite programmingstable sets0/1 linear programmingPayley graphs

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Semidefinite programming (90C22)

Related Items

\(k\)-point semidefinite programming bounds for equiangular lines, New heuristics for the vertex coloring problem based on semidefinite programming, Partial Lasserre relaxation for sparse Max-Cut, Symmetric sums of squares over \(k\)-subset hypercubes, Invariant Semidefinite Programs, Mixed-integer nonlinear optimization: a hatchery for modern mathematics. Abstracts from the workshop held June 2--8, 2019

Uses Software

• CSDP

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Strengthened semidefinite programming bounds for codes
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• A lift-and-project cutting plane algorithm for mixed 0-1 programs
• A note on the stability number of an orthogonality graph
• An Explicit Equivalent Positive Semidefinite Program for Nonlinear 0-1 Programs
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• The Operator $\Psi$ for the Chromatic Number of a Graph
• Computing Semidefinite Programming Lower Bounds for the (Fractional) Chromatic Number Via Block-Diagonalization
• Cones of Matrices and Set-Functions and 0–1 Optimization
• On the Shannon capacity of a graph
• CSDP, A C library for semidefinite programming
• Paths in graphs
• A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming