Branch-and-cut for the k-way equipartition problem
Download the paper,
postscript or pdf.
Author:
John E. Mitchell
Department of Mathematical Sciences
Rensselaer Polytechnic Institute
Troy, NY 12180 USA
mitchj@rpi.edu
January 19, 2001.
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.
Download the paper,
postscript or pdf.
Return to my list of papers.