LP and SDP branch-and-cut algorithms for the minimum graph bisection problem: a computational comparison

  • 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.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Michael Armbruster, Marzena Fügenschuh, Christoph Helmberg, Alexander Martin
DOI:https://doi.org/10.1007/s12532-012-0040-5
ISSN:1867-2949
Parent Title (English):Mathematical Programming Computation
Publisher:Springer Science and Business Media LLC
Document Type:Article
Language:English
Year of Completion:2012
Tag:Software; Theoretical Computer Science
Volume:4
Issue:3
Page Number:32
First Page:275
Last Page:306
Mathematical Programming Computation :MPC 2012 - Issue 3
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.