An exact approach for the balanced k-way partitioning problem with weight constraints and its application to sports team realignment

Diego Recalde (), Daniel Severín (), Ramiro Torres () and Polo Vaca ()
Additional contact information
Diego Recalde: Escuela Politécnica Nacional
Daniel Severín: Universidad Nacional de Rosario and CONICET
Ramiro Torres: Escuela Politécnica Nacional
Polo Vaca: Escuela Politécnica Nacional

Journal of Combinatorial Optimization, 2018, vol. 36, issue 3, No 13, 916-936

Abstract: Abstract In this work a balanced k-way partitioning problem with weight constraints is defined to model the sports team realignment. Sports teams must be partitioned into a fixed number of groups according to some regulations, where the total distance of the road trips that all teams must travel to play a double round robin tournament in each group is minimized. Two integer programming formulations for this problem are introduced, and the validity of three families of inequalities associated to the polytope of these formulations is proved. The performance of a tabu search procedure and a branch and cut algorithm, which uses the valid inequalities as cuts, is evaluated over simulated and real-world instances. In particular, an optimal solution for the realignment of the Ecuadorian football league is reported and the methodology can be suitable adapted for the realignment of other sports leagues.

Keywords: Integer programming models; Graph partitioning; Tabu search; Sports team realignment (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-018-0254-1 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:36:y:2018:i:3:d:10.1007_s10878-018-0254-1

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-018-0254-1

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().