Abstract
In the second category of the Ecuadorian football league, a set of football teams must be grouped into \(k\) geographical zones 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 zone is minimized. This problem can be modeled as a \(k\)-clique partitioning problem with constraints on the sizes and weights of the cliques. An integer programming formulation and a heuristic approach were developed to provide a solution to the problem which has been implemented in the 2015 edition of the aforementioned football championship.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Grötschel, M., Wakabayashi, Y.: A cutting plane algorithm for a clustering problem. Math. Program. 45, 59–96 (1989)
Jaehn, F., Pesch, E.: New bounds and constraint propagation techniques for the clique partitioning problem. Discrete Appl. Math. 161, 2025–2037 (2013)
Ferreira, C., Martin, A., de Souza, C., Weismantel, R., Wolsey, L.: The node capacitated graph partitioning problem: a computational study. Math. Program. 81, 229–256 (1998)
Furmanczyk, H., Kubale, M.: Equitable coloring of graphs. In: Graph Colorings, Providence, Rhode Island, pp. 35–53. American Mathematical Society (2004)
Labbé, M., Özsoy, F.A.: Size-constrained graph partitioning polytopes. Discrete Math. 310, 3473–3493 (2010)
McDonald, B., Pulleyblank, W.: Realignment in the NHL, MLB, NFL, and NBA. J. Quant. Anal. Sports 10, 225–240 (2014)
Mitchell, J.: Branch-and-cut for the k-way equipartition problem. Technical report, Department of Mathematical Sciences, Rensselaer Polytechnic Institute (2001)
Ji, X., Mitchell, J.E.: Finding optimal realignments in sports leagues using a branch-and-cut-and-price approach. Int. J. Oper. Res. 1, 101–122 (2005)
Ji, X., Mitchell, J.E.: Branch-and-price-and-cut on the clique partitioning problem with minimum clique size requirement. Discrete Optim. 4, 87–102 (2007)
Recalde, D., Torres, R., Vaca, P.: Scheduling the professional ecuadorian football league by integer programming. Comput. Oper. Res. 40, 2478–2484 (2013)
Saltzman, R., Bradford, R.M.: Optimal realignments of the teams in the National Football League. Eur. J. Oper. Res. 93, 469–475 (1996)
Test instances for the football team realignment in Ecuador. http://www.math.epn.edu.ec/~recalde/#TestInstances/
Acknowledgments
We thank Patricio Torres, authority of the team Liga Deportiva Universitaria, and Galo Barreto, former manager of AFNA, for their support to this project. This research was partially supported by the PACK-COVER MATH-AmSud cooperation project.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this paper
Cite this paper
Recalde, D., Severín, D., Torres, R., Vaca, P. (2016). Balanced Partition of a Graph for Football Team Realignment in Ecuador. In: Cerulli, R., Fujishige, S., Mahjoub, A. (eds) Combinatorial Optimization. ISCO 2016. Lecture Notes in Computer Science(), vol 9849. Springer, Cham. https://doi.org/10.1007/978-3-319-45587-7_31
Download citation
DOI: https://doi.org/10.1007/978-3-319-45587-7_31
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-45586-0
Online ISBN: 978-3-319-45587-7
eBook Packages: Computer ScienceComputer Science (R0)