Engineering Branch-and-Cut Algorithms for the Equicut Problem

Beitrag in einem Sammelwerk
(Originalarbeit)


Details zur Publikation

Autorinnen und Autoren: Anjos M, Liers F, Pardella GL, Schmutzer A
Herausgeber: Karoly Bezdek, Antoine Deza, Yinyu Ye
Titel Sammelwerk: Discrete Geometry and Optimization
Verlag: Springer
Verlagsort: Berlin Heidelberg
Jahr der Veröffentlichung: 2013
Titel der Reihe: Fields Institute Communications
Band: 69
Seitenbereich: 17-32
ISBN: 978-3-319-00199-9


Abstract


A minimum equicut of an edge-weighted graph is a partition of the nodes of the graph into two sets of equal size such that the sum of the weights of edges joining nodes in different partitions is minimum. We compare basic linear and semidefinite relaxations for the equicut problem, and find that linear bounds are competitive with the corresponding semidefinite ones but can be computed much faster. Motivated by an application of equicut in theoretical physics, we revisit an approach by Brunetta et al. and present an enhanced branch-and-cut algorithm. Our computational results suggest that the proposed branch-and-cut algorithm has a better performance than the algorithm of Brunetta et al. Further, it is able to solve to optimality in reasonable time several instances with more than 200 nodes from the physics application.



FAU-Autorinnen und Autoren / FAU-Herausgeberinnen und Herausgeber

Liers-Bergmann, Frauke Prof. Dr.
Professur für Angewandte Mathematik (Ganzzahlige und robuste Optimierung)
Schmutzer, Andreas
Professur für Angewandte Mathematik (Ganzzahlige und robuste Optimierung)


Einrichtungen weiterer Autorinnen und Autoren

Universität Köln
University of Waterloo (UW)


Zitierweisen

APA:
Anjos, M., Liers, F., Pardella, G.L., & Schmutzer, A. (2013). Engineering Branch-and-Cut Algorithms for the Equicut Problem. In Karoly Bezdek, Antoine Deza, Yinyu Ye (Eds.), Discrete Geometry and Optimization (pp. 17-32). Berlin Heidelberg: Springer.

MLA:
Anjos, Miguel, et al. "Engineering Branch-and-Cut Algorithms for the Equicut Problem." Discrete Geometry and Optimization Ed. Karoly Bezdek, Antoine Deza, Yinyu Ye, Berlin Heidelberg: Springer, 2013. 17-32.

BibTeX: 

Zuletzt aktualisiert 2018-11-08 um 01:44