A program that produces the optimal pairings for a round-robin chess tournament taking into account player preferences.
Traditional chess round-robin tournaments have players face every other player once during the tournament. The pairings are thus decided beforehand for all rounds, instead of being dependent on previous results, such as swiss systems.
Usually, a round takes place at a certain time, with all players playing at once. For pairings to be valid, they need to ensure that a player must have only a single game every round and play every other player exactly once. Additionally we enforce that for a given player, the amount of games played with each color is equal. The problem is not trivial, but there exist simple and fast scheduling algorithms to solve it (e.g. the circle method).
When there is an odd number of players, every player will be resting once during the tournament. This is usually determined randomly, but we consider the case where players are asked beforehand about their preferences for which round they would like to rest, and build a pairing maximizing the total satisfaction.
The project consists of 3 distinct parts:
- An integer linear programming model: this is coded in OPL and efficiently finds the optimal solution for the given input data. However, due to the complexity of the problem, it does not scale very well for large sets of data and in our experiments it is too slow for tournaments with >20 players (rarely seen in practice).
- Heuristic models: an alternative to the previous one, which does not guarantee finding the global optimum, but produces a good enough solution in a short amount of time, even for large tournaments. Different algorithms are presented, raning from a simple Greedy one, to an advanced GRASP implementation, where the different hyperparameters have been fine-tuned.
- Instance generator: a Python script that produces random input data of the specified size, to be used as input for the previous solvers as a means of benchmarking.