Engineering Branch-and-Cut Algorithms for the Equicut Problem

Anjos M, Liers F, Pardella GL, Schmutzer A (2013)

Publication Type: Book chapter / Article in edited volumes

Publication year: 2013

Publisher: Springer

Edited Volumes: Discrete Geometry and Optimization

Series: Fields Institute Communications

City/Town: Berlin Heidelberg

Book Volume: 69

Pages Range: 17-32

ISBN: 978-3-319-00199-9

DOI: 10.1007/978-3-319-00200-2_2


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.

Authors with CRIS profile

Involved external institutions

How to cite


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.


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: Download