Optimizing over the cut cone: A new polyhedral algorithm for the maximum-weight cut problem

[摘要] Polyhedral cutting-plane algorithms for hard combinatorial problems have scored notable successes. However, computational research on the Maximum-Weight Cut Problem (MCP) on undirected graphs has been inconclusive. In 1988, Barahona suggested a new polyhedral algorithm that, given a good initial solution, attempts to prove optimality. If the initial cut is non-optimal, it is iteratively improved until optimal. The expected advantages are three-fold. If a good, fast heuristic is used, an optimal solution may be available. The algorithm can then prove optimality fast. Secondly, if time is a serious constraint, prematurely terminating the algorithm yields a cut at least as good as the original. Finally, since the algorithm nominally optimizes over the cut cone rather than the cut polytope, the underlying separation problem is very simple. This research explores Barahona;;s algorithm on a class of MCP instances arising in statistical mechanics. The graphs are toroidal grids, together with an additional universal vertex. By considering different integer programming formulations, it has been possible to design a fast algorithm that replaces optimization over the cut polytope by repeated optimization over the intersection of the cut cone and the unit cube. This latter polyhedron is shown to be equivalent to the multicut polytope, and its basic facet classes are identified. The final algorithm is successful in solving MCP instances over 70 x 70 grids, over 5 times bigger than previous algorithms. Substantial improvements in computation time have also been achieved.

[发布机构] Rice University

[效力级别] Mathematics