Branch-and-cut for the k-way equipartition problem

John E. Mitchell (mitchjrpi.edu)

Abstract: We investigate the polyhedral structure of a formulation of the k-way equipartition problem and a branch-and-cut algorithm for the problem. The k-way equipartition problem requires dividing the vertices of a weighted graph into k equally sized sets, so as to minimize the total weight of edges that have both endpoints in the same set. Applications of the k-way equipartition problem arise in diverse areas including network design and sports scheduling. We describe computational results with a branch-and-cut algorithm.

Keywords: graph equipartition, branch-and-cut, network design, realignment, clustering

Category 1: Combinatorial Optimization (Polyhedra )

Category 2: Integer Programming (Cutting Plane Approaches )

Citation: Department of Mathematical Sciences Rensselaer Polytechnic Institute Troy, NY 12180 USA January 2001 http://www.rpi.edu/~mitchj/papers/kequi.html

Download: [Postscript][PDF]

Entry Submitted: 02/28/2001
Entry Accepted: 02/28/2001
Entry Last Modified: 07/23/2002

Modify/Update this entry