Solving k-Way Graph Partitioning Problems to Optimality: The Impact of Semidefinite Relaxations and the Bundle Method

Miguel F. Anjos (), Bissan Ghaddar (), Lena Hupp (), Frauke Liers () and Angelika Wiegele ()
Additional contact information
Miguel F. Anjos: École Polytechnique de Montréal, Canada Research Chair in Discrete Nonlinear Optimization in Engineering, GERAD
Bissan Ghaddar: Department of National Defence, Centre for Operational Research and Analysis, Defence Research and Development Canada
Lena Hupp: Friedrich-Alexander-Universität Erlangen-Nürnberg, Department Mathematik
Frauke Liers: Friedrich-Alexander-Universität Erlangen-Nürnberg, Department Mathematik
Angelika Wiegele: Alpen-Adria-Universität Klagenfurt, Institut für Mathematik

A chapter in Facets of Combinatorial Optimization, 2013, pp 355-386 from Springer

Abstract: Abstract This paper is concerned with computing global optimal solutions for maximum k-cut problems. We improve on the SBC algorithm of Ghaddar, Anjos and Liers in order to compute such solutions in less time. We extend the design principles of the successful BiqMac solver for maximum 2-cut to the general maximum k-cut problem. As part of this extension, we investigate different ways of choosing variables for branching. We also study the impact of the separation of clique inequalities within this new framework and observe that it frequently reduces the number of subproblems considerably. Our computational results suggest that the proposed approach achieves a drastic speedup in comparison to SBC, especially when k=3. We also made a comparison with the orbitopal fixing approach of Kaibel, Peinhardt and Pfetsch. The results suggest that, while their performance is better for sparse instances and larger values of k, our proposed approach is superior for smaller k and for dense instances of medium size. Furthermore, we used CPLEX for solving the ILP formulation underlying the orbitopal fixing algorithm and conclude that especially on dense instances the new algorithm outperforms CPLEX by far.

Keywords: Valid Inequality; Interior Point Method; Edge Density; Bundle Method; Integer Linear Programming Model (search for similar items in EconPapers)
Date: 2013
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-642-38189-8_15

Ordering information: This item can be ordered from
http://www.springer.com/9783642381898

DOI: 10.1007/978-3-642-38189-8_15

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().