Engineering Branch-and-Cut Algorithms for the Equicut Problem

Anjos, Miguel F. and Liers, Frauke and Pardella, Gregor and Schmutzer, Andreas (2013) Engineering Branch-and-Cut Algorithms for the Equicut Problem.
Published in: Discrete Geometry and Optimization., Fields Institute Communications. 69 Springer 2013.


A minimum equicut of an edge-weighted graph is a partition of the nodes of the graph into two sets of equal size such hat the sum of the weights of edges joining nodes in different partitions is minimum. We compare basic linear and semidefnite relaxations for the equicut problem, and and that linear bounds are competitive with the corresponding semidefnite 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-andcut 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.

Download: [img] PDF - Submitted Version Restricted to Repository staff only
Download (313kB) | Request a copy
Editorial actions: View Item View Item (Login required)
Content information:
Deposit Information:
Depositing User: Andreas Schmutzer
Date Deposited: 10 May 2012 13:51
Last Modified: 14 Aug 2013 12:04