swMATH ID: 4782
Software Authors: Burer, Samuel; Monteiro, Renato D. C.; Zhang, Yin
Description: Rank-two relaxation heuristics for MAX-CUT and other binary quadratic programs The Goemans–Williamson randomized algorithm guarantees a high-quality approximation to the MAX-CUT problem, but the cost associated with such an approximation can be excessively high for large-scale problems due to the need for solving an expensive semidefinite relaxation. In order to achieve better practical performance, we propose an alternative, rank-two relaxation and develop a specialized version of the Goemans–Williamson technique. The proposed approach leads to continuous optimization heuristics applicable to MAX-CUT as well as other binary quadratic programs, for example the MAX-BISECTION problem.par A computer code based on the rank-two relaxation heuristics is compared with two state-of-the-art semidefinite programming codes that implement the Goemans–Williamson randomized algorithm, as well as with a purely heuristic code for effectively solving a particular MAX-CUT problem arising in physics. Computational results show that the proposed approach is fast and scalable and, more importantly, attains a higher approximation quality in practice than that of the Goemans–Williamson randomized algorithm. An extension to MAX-BISECTION is also discussed, as is an important difference between the proposed approach and the Goemans–Williamson algorithm; namely, that the new approach does not guarantee an upper bound on the MAX-CUT optimal value.
Homepage: http://www.caam.rice.edu/~zhang/circut/
Keywords: binary quadratic programs; MAX-CUT and MAX-BISECTION; semidefinite relaxation; rank-two relaxation; continuous optimization heuristics
Related Software: Outward rotations; SDPLR; Tabu search; COL; SeDuMi; Biq Mac; SDPpack; DIMACS; SDPA; Max-AO; SDPT3; TTTPLOTS; Scatter Search; PERL; GRASP; OR-Library; BARON; Benchmarks for Optimization Software; NOA; LaGO
Cited in: 42 Publications

Citations by Year