Integer programming models for round robin tournaments

doi:10.1016/j.ejor.2023.02.017

Integer programming models for round robin tournaments

2023-10-01

3

OA

AI

J

Jasper van Doornmalen

DOI：10.1016/j.ejor.2023.02.017

原文链接

查看原文

摘要

En 中文

Round robin tournaments are omnipresent in sport competitions and beyond. We investigate three in-teger 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 formu-lation. 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. (c) 2023 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license ( http://creativecommons.org/licenses/by/4.0/ )

Keyword:

Integer programming

OR in sports

Cutting planes

Branch-and-price

Integer programming models for round robin tournaments

摘要

AI总结

期刊

机构