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.

Frauke Liers-Bergmann
Professur für Optimization under Uncertainty & Data Analysis
Andreas Schmutzer
Professur für Optimization under Uncertainty & Data Analysis

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