Optimization Online


LP and SDP Branch-and-Cut Algorithms for the Minimum Graph Bisection Problem: A Computational Comparison

Michael Armbruster (helmberg***at***mathematik.tu-chemnitz.de)
Christoph Helmberg (helmberg***at***mathematik.tu-chemnitz.de)
Marzena Fuegenschuh (fuegenschuh***at***beuth-hochschule.de)
Alexander Martin (alexander.martin***at***math.uni-erlangen.de)

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 semidefinite relaxations via the spectral bundle method, which allows to exploit structural properties like sparsity. In order to evaluate the relative strengths of linear and semidefinite 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 profits 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.

Keywords: branch and cut algorithms, cutting plane algorithms, polyhedral combinatorics, semidefinite programs

Category 1: Combinatorial Optimization (Branch and Cut Algorithms )

Category 2: Combinatorial Optimization (Polyhedra )

Citation: March 2011

Download: [PDF]

Entry Submitted: 03/03/2011
Entry Accepted: 03/03/2011
Entry Last Modified: 12/20/2011

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society