Block-diagonal semidefinite programming hierarchies for 0/1 programming

DOI10.1016/J.ORL.2008.10.003MaRDI QIDQ1002080zbMATH OpenOpenAlexFDO

Authors Nebojša Gvozdenović, Monique Laurent, 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, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.156.9619

zbMATH Keywords

semidefinite programmingstable sets0/1 linear programmingPayley graphs

Mathematics Subject Classification ID

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

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 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.

Recommendations

• Semidefinite programming hierarchies for constrained bilinear optimization
• Block coordinate descent methods for semidefinite programming
• A numerical algorithm for block-diagonal decomposition of matrix \(*\)-algebras with application to semidefinite programming
• Numerical block diagonalization of matrix \(\ast\)-algebras with application to semidefinite programming
• Semidefinite programming
• scientific article; zbMATH DE number 1047682
• Semidefinite programming
• Semidefinite Programming
• Implementation of a block-decomposition algorithm for solving large-scale conic semidefinite programming problems
• Block-Iterative Algorithms with Diagonally Scaled Oblique Projections for the Linear Feasibility Problem

Cites work

• scientific article; zbMATH DE number 3470175 (Why is no real title available?)
• scientific article; zbMATH DE number 1416629 (Why is no real title available?)
• A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• 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
• CSDP, A C library for semidefinite programming
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• 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
• Paths in graphs
• Semidefinite programming and integer programming
• Strengthened semidefinite programming bounds for codes
• The Operator $\Psi$ for the Chromatic Number of a Graph

Cited in

(8)

• On different versions of the exact subgraph hierarchy for the stable set problem
• Symmetric sums of squares over \(k\)-subset hypercubes
• Partial Lasserre relaxation for sparse Max-Cut
• New heuristics for the vertex coloring problem based on semidefinite programming
• \(k\)-point semidefinite programming bounds for equiangular lines
• A new semidefinite programming hierarchy for cycles in binary matroids and cuts in graphs
• Mixed-integer nonlinear optimization: a hatchery for modern mathematics. Abstracts from the workshop held June 2--8, 2019
• Invariant Semidefinite Programs

Describes a project that uses

Uses Software

• CSDP

This page was built for publication: Block-diagonal semidefinite programming hierarchies for 0/1 programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1002080)