Integer programming models for round robin tournaments

Jasper van Doornmalen, Christopher Hojny, Roel Lambers and Frits C.R. Spieksma

European Journal of Operational Research, 2023, vol. 310, issue 1, 24-33

Abstract: Round robin tournaments are omnipresent in sport competitions and beyond. We investigate three integer programming formulations for scheduling a round robin tournament, one of which we call the matching formulation. We analytically compare their linear relaxations, and find that the relaxation of the matching formulation is stronger than the other relaxations, while still being solvable in polynomial time. In addition, we provide an exponentially sized class of valid inequalities for the matching formulation. Complementing our theoretical assessment of the strength of the different formulations, we also experimentally show that the matching formulation is superior on a broad set of instances. Finally, we describe a branch-and-price algorithm for finding round robin tournaments that is based on the matching formulation.

Keywords: Integer programming; OR in sports; Cutting planes; Branch-and-price (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221723001510
Full text for ScienceDirect subscribers only

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:eee:ejores:v:310:y:2023:i:1:p:24-33

DOI: 10.1016/j.ejor.2023.02.017

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().