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.
Citation
Department of Mathematical Sciences Rensselaer Polytechnic Institute Troy, NY 12180 USA January 2001 http://www.rpi.edu/~mitchj/papers/kequi.html