TL;DR
This paper introduces two novel integer programming formulations for scheduling round robin tournaments, with one formulation demonstrating superior performance in terms of LP relaxation strength. The authors also present a branch-and-price algorithm that effectively solves smaller instances, highlighting the practical utility of their theoretical advancements.
What Problem Does This Paper Address?
Scheduling round robin tournaments, where every participant plays every other participant a set number of times, is a common and complex problem in sports and other domains. The goal is to create a schedule that is fair, efficient, and adheres to various constraints. Integer programming (IP) has emerged as a powerful tool for tackling this challenge, allowing for the modeling of intricate constraints. However, existing IP formulations can be computationally expensive. This paper aims to improve upon existing IP models by developing new formulations that are both theoretically stronger and practically more efficient for solving round robin tournament scheduling problems.
Methods
The authors propose two new integer programming formulations for the Single Round Robin (SRR) tournament: the "matching formulation" and the "permutation formulation." They then compare these to a well-established "traditional formulation."
- Traditional Formulation: This is a standard IP model that uses binary variables to indicate whether a specific match is played in a specific round. It has a polynomial number of variables and constraints.
- Matching Formulation: This novel approach views a round of a tournament as a perfect matching in a complete graph where nodes represent teams. It uses binary variables to represent entire matchings for each round. This formulation has an exponential number of variables but, crucially, its linear programming (LP) relaxation can be solved in polynomial time.
- Permutation Formulation: Another new formulation that models the order of opponents for each team. Similar to the matching formulation, it has an exponential number of variables but its LP relaxation is also polynomially solvable.
The paper rigorously analyzes the strength of these formulations by comparing the values of their LP relaxations. They also introduce a class of valid inequalities to further strengthen the matching formulation. Finally, they develop and implement a branch-and-price algorithm based on the matching formulation to solve the integer programming problem.
Datasets
The authors generated 1000 instances of the SRR problem for evaluation. These instances were parameterized by the number of teams ($n \in \{6, 12, 18, 24\}$) and the density of match-round pairs with non-zero costs ($p \in \{0.5, 0.6, 0.7, 0.8, 0.9\}$). The cost coefficients were binary (0 or 1). The instances are publicly available.
Key Insights and Ideas
- The Matching Formulation is Stronger: The matching formulation's LP relaxation provides significantly tighter bounds than the traditional formulation, especially for larger numbers of teams and denser problem instances. This means it gets closer to the optimal integer solution, potentially reducing the search space for solvers.
- Polynomial Solvability of LP Relaxations: Despite having an exponential number of variables, the LP relaxations of the matching and permutation formulations can be solved efficiently in polynomial time. This is a critical finding, as it makes these formulations computationally tractable.
- Special Case for n=4: For a small number of teams (n=4), all three formulations (traditional, matching, and permutation) become relaxation-equivalent, and the matching formulation's integer hull is integral, meaning solving its LP relaxation directly yields the optimal integer solution.
- Branch-and-Price Efficiency: The implemented branch-and-price algorithm, leveraging the stronger matching formulation, can solve smaller instances very efficiently, demonstrating the practical benefits of the theoretical advancements.
Key Results
- LP Relaxation Comparison: For $n \ge 6$, the matching formulation is strictly stronger than the traditional and permutation formulations. The paper quantifies this by showing how much of the "gap" between the traditional LP relaxation and the optimal integer solution is closed by the matching formulation's LP relaxation. For instance, for $n=18$ and $p=0.9$, the matching formulation closes an average of 21.55% of the gap.
- Computational Performance: The branch-and-price algorithm based on the matching formulation solved instances with 6 and 12 teams very quickly (fractions of a second to seconds). Instances with 18 teams were more challenging, with some taking up to 2 hours to solve, but still demonstrating reasonable performance.
- Instance Generation: The paper introduces a systematic way to generate SRR instances with varying difficulty, which is valuable for benchmarking future research.
Limitations and Future Work
- Large Instances Remain Challenging: While the branch-and-price algorithm performs well on smaller instances, solving large-scale SRR problems efficiently remains a challenge.
- Further Strengthening of Formulations: The authors suggest exploring additional cutting planes to further strengthen both the traditional and matching formulations. This could particularly impact the pricing problem within the branch-and-price algorithm.
- Sophisticated Branching Rules and Heuristics: Future work could focus on developing more advanced branching rules or heuristics to improve the efficiency of the branch-and-price algorithm, especially for larger instances.
- Separation of Inequalities: The complexity of efficiently separating the class of inequalities proposed in Proposition 4.3 is left open for future research.
Summary updated