LP and SDP Branch-and-Cut Algorithms for the Minimum Graph Bisection Problem: A Computational Comparison
Armbruster M, Fügenschuh M, Helmberg C, Martin A (2012)
Publication Language: English
Publication Type: Journal article
Publication year: 2012
Journal
Publisher: Springer Verlag
Book Volume: 4
Pages Range: 275 -- 306
Abstract
While semidefinite relaxations are known to deliver good approximations for combinatorial optimization problems like graph bisection, their practical scope is mostly associated with small dense instances. For large sparse instances, cutting plane techniques are considered the method of choice. These are also applicable for semi- definite relaxations via the spectral bundle method, which allows to exploit structural properties like sparsity. In order to evaluate the relative strengths of linear and semi- definite approaches for large sparse instances, we set up a common branch and-cut framework for linear and semidefinite relaxations of the minimum graph bisection problem. It incorporates separation algorithms for valid inequalities of the bisection cut polytope described in a recent study by the authors. While the problem specific cuts help to strengthen the linear relaxation significantly, the semidefinite bound prof- its much more from separating the cycle inequalities of the cut polytope on a slightly enlarged support. Extensive numerical experiments show that this semidefinite branch- and-cut approach without problem specific cuts is a superior choice to the classical simplex approach exploiting bisection specific inequalities on a clear majority of our large sparse test instances from VLSI design and numerical optimization.
Authors with CRIS profile
Involved external institutions
Germany (DE)How to cite
APA:
Armbruster, M., Fügenschuh, M., Helmberg, C., & Martin, A. (2012). LP and SDP Branch-and-Cut Algorithms for the Minimum Graph Bisection Problem: A Computational Comparison. Mathematical Programming Computation, 4, 275 -- 306.
MLA:
Armbruster, Michael, et al. "LP and SDP Branch-and-Cut Algorithms for the Minimum Graph Bisection Problem: A Computational Comparison." Mathematical Programming Computation 4 (2012): 275 -- 306.
BibTeX: Download