A BRANCH-AND-CUT ALGORITHM FOR THE EQUICUT PROBLEM

We describe an algorithm for solving the equicut problem on complete g raphs, The core of the algorithm is a cutting-plane procedure that exp loits a subset of the linear inequalities defining the convex hull of the incidence vectors of the edge sets that define an equicut. The cut s are generated by several separation procedures that will be describe d in the paper. Whenever the cutting-plane procedure does not terminat e with an optimal solution, the algorithm uses a branch-and-cut strate gy. We also describe the implementation of the algorithm and the inter face with the LP solver. Finally, we report on computational results o n dense instances with sizes up to 100 nodes. (C) 1997 The Mathematica l Programming Society, Inc. Published by Elsevier Science B.V.