Groupe d’études et de recherche en analyse des décisions

G-2012-15

Engineering Branch-and-Cut Algorithms for the Equicut Problem

, , et

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.

, 17 pages