Finding optimal realignments in sports leagues using a branch-and-cut-and-price approach

Xiaoyun Ji (jixrpi.edu)
John E Mitchell (mitchjrpi.edu)

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.

Keywords: Realignment, graph equipartition, branch-and-price, clustering, micro-a ggregation

Category 1: Combinatorial Optimization (Branch and Cut Algorithms )

Category 2: Applications -- OR and Management Sciences

Citation: Mathematical Sciences, RPI, Troy, NY 12180. February 15, 2005. http://www.rpi.edu/~mitchj/papers/AlignPrice.html

Download: [PDF]

Entry Submitted: 02/17/2005
Entry Accepted: 02/17/2005
Entry Last Modified: 02/17/2005

Modify/Update this entry