A NEW SECOND-ORDER CONE PROGRAMMING RELAXATION FOR MAX-CUT PROBLEMS

DOI10.15807/jorsj.46.164zbMath1109.90337OpenAlexW2147191663MaRDI QIDQ4446320

Tsunehiro Suzuki, Masakazu Muramatsu

Publication date: 26 January 2004

Published in: Journal of the Operations Research Society of Japan (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.15807/jorsj.46.164

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27)

Related Items (max. 100)

Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations ⋮ Using a mixed integer quadratic programming solver for the unconstrained quadratic \(0-1\) problem ⋮ SpeeDP: an algorithm to compute SDP bounds for very large max-cut instances ⋮ A new global algorithm for max-cut problem with chordal sparsity ⋮ Penalized semidefinite programming for quadratically-constrained quadratic optimization ⋮ A simultaneous diagonalization based SOCP relaxation for convex quadratic programs with linear complementarity constraints

Uses Software

• SDPA
• SeDuMi

This page was built for publication: A NEW SECOND-ORDER CONE PROGRAMMING RELAXATION FOR MAX-CUT PROBLEMS