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

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