A bundle approach for SDPs with exact subgraph constraints

DOI10.1007/978-3-030-17953-3_16MaRDI QIDQ2293089zbMATH OpenOpenAlexFDO

Authors Elisabeth Gaar, Franz Rendl

Publication date 6 February 2020

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

zbMATH Keywords

semidefinite programmingcoloringmax-cutstable setrelaxation hierarchy

Mathematics Subject Classification ID

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

Abstract: The 'exact subgraph' approach was recently introduced as a hierarchical scheme to get increasingly tight semidefinite programming relaxations of several NP-hard graph optimization problems. Solving these relaxations is a computational challenge because of the potentially large number of violated subgraph constraints. We introduce a computational framework for these relaxations designed to cope with these difficulties. We suggest a partial Lagrangian dual, and exploit the fact that its evaluation decomposes into two independent subproblems. This opens the way to use the bundle method from non-smooth optimization to minimize the dual function. Computational experiments on the Max-Cut, stable set and coloring problem show the efficiency of this approach.

Recommendations

• A computational study of exact subgraph based SDP bounds for max-cut, stable set and coloring
• Computational experience with a bundle approach for semidefinite cutting plane relaxations of Max-Cut and equipartition
• A spectral bundle method with bounds
• Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations
• scientific article; zbMATH DE number 1187169

Cited in

(8)

• A Hierarchy of Subgraph Projection-Based Semidefinite Relaxations for Some NP-Hard Graph Optimization Problems
• On different versions of the exact subgraph hierarchy for the stable set problem
• Improving ADMMs for solving doubly nonnegative programs through dual factorization
• A spectral bundle method with bounds
• Strong SDP based bounds on the cutwidth of a graph
• A computational study of exact subgraph based SDP bounds for max-cut, stable set and coloring
• scientific article; zbMATH DE number 1187169 (Why is no real title available?)
• An SDP-based approach for computing the stability number of a graph

This page was built for publication: A bundle approach for SDPs with exact subgraph constraints

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