A Comparative Study of Linear and Semidefinite Branch-and-Cut Methods for Solving the Minimum Graph Bisection Problem

Armbruster M, Helmberg C, Fügenschuh M, Martin A (2008)

Publication Language: English

Publication Type: Book chapter / Article in edited volumes

Publication year: 2008

Edited Volumes: Integer Programming and Combinatorial Optimization

Series: Proceedings of the IPCO 2008 Conference, LNCS 5035

Pages Range: 112 -- 124

Conference Proceedings Title: Integer Programming and Combinatorial Optimization

Abstract

Semidefinite relaxations are known to deliver good approximations for combinatorial optimization problems like graph bisection. Using the spectral bundle method it is possible to exploit structural properties of the underlying problem and to apply, even to sparse large scale instances, cutting plane methods, probably the most successful technique in linear programming. 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 presented in the recent study [2] of the facial structure of the associated polytope. Extensive numerical experiments show that the semidefinite branch-and-cut approach outperforms the classical simplex approach on a clear majority of the sparse large scale test instances. On instances from compiler design the simplex approach is faster.

Authors with CRIS profile

Alexander Martin Economics - Discrete Optimization - Mathematics (EDOM)

Involved external institutions

Technische Universität Chemnitz DE Germany (DE) Beuth Hochschule für Technik Berlin DE Germany (DE)

How to cite

APA:

Armbruster, M., Helmberg, C., Fügenschuh, M., & Martin, A. (2008). A Comparative Study of Linear and Semidefinite Branch-and-Cut Methods for Solving the Minimum Graph Bisection Problem. In A. Lodi, A. Panconesi, G. Renaldi (Eds.), Integer Programming and Combinatorial Optimization. (pp. 112 -- 124).

MLA:

Armbruster, Michael, et al. "A Comparative Study of Linear and Semidefinite Branch-and-Cut Methods for Solving the Minimum Graph Bisection Problem." Integer Programming and Combinatorial Optimization. Ed. A. Lodi, A. Panconesi, G. Renaldi, 2008. 112 -- 124.

BibTeX: Download