A Branch and Bound Algorithm for Max-Cut Based on Combining Semidefinite and Polyhedral Relaxations

DOI10.1007/978-3-540-72792-7_23zbMath1136.90461OpenAlexW2132400628MaRDI QIDQ5429275

Franz Rendl, Giovanni Rinaldi, Angelika Wiegele

Publication date: 29 November 2007

Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-72792-7_23

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27)

Related Items (14)

Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations ⋮ Speeding up IP-based algorithms for constrained quadratic 0-1 optimization ⋮ Generating cutting planes for the semidefinite relaxation of quadratic programs ⋮ Exact Facetial Odd-Cycle Separation for Maximum Cut and Binary Quadratic Optimization ⋮ A Comparative Study of Linear and Semidefinite Branch-and-Cut Methods for Solving the Minimum Graph Bisection Problem ⋮ An exact solution method for unconstrained quadratic 0--1 programming: a geometric approach ⋮ A branch-and-cut algorithm based on semidefinite programming for the minimum \(k\)-partition problem ⋮ Convex relaxations of non-convex mixed integer quadratically constrained programs: projected formulations ⋮ An Iterative Scheme for Valid Polynomial Inequality Generation in Binary Polynomial Programming ⋮ Parametric Lagrangian dual for the binary quadratic programming problem ⋮ Computational experience with a SDP-based algorithm for maximum cut with limited unbalance ⋮ Spectral bounds for unconstrained \((- 1,1)\)-quadratic optimization problems ⋮ Global Approaches for Facility Layout and VLSI Floorplanning ⋮ A sublevel moment-SOS hierarchy for polynomial optimization

Uses Software

• OR-Library

This page was built for publication: A Branch and Bound Algorithm for Max-Cut Based on Combining Semidefinite and Polyhedral Relaxations