Finding optimal realignments in sports leagues using a
branch-and-cut-and-price approach
Download the paper,
in pdf.
Authors:
Xiaoyun Ji
Department of Mathematical Sciences
Rensselaer Polytechnic Institute
Troy, NY 12180 USA
jix@rpi.edu
John E. Mitchell
Department of Mathematical Sciences
Rensselaer Polytechnic Institute
Troy, NY 12180 USA
mitchj@rpi.edu
February 15, 2005.
Abstract:
The sports team realignment problem can be modelled as $k$-way equipartition:
given a complete graph $K_{n}=(V,E)$, with edge weight $c_{e}$ on each edge,
partition the vertices $V$ into $k$ divisions that have exactly $S$ vertices,
so as to minimize the total weight of the edges that have both
endpoints in the same division.
In this paper, we discuss solving $k$-way equipartition
problem using branch-and-price scheme.
We demonstrated the necessity of cutting planes for this problem
and suggested an effective way of adding cutting planes in
the branch-and-price framework. We solved the pricing subproblem
as an integer programming problem.
Using this method, we found the optimal realignment solution for
three major professional sports leagues in North America
(basketball, hockey, football). We also present
computational results on some
larger randomly generated micro-aggregation problems.
Download the paper,
in pdf.
International
Journal of Operational Research (IJOR),
Volume 1, Numbers 1-2,
pages 101-122,
2005.
Optimization Online listing
Return to my list of papers.