Models and algorithms for the scheduling of a doubles tennis training tournament

Abstract

We address a doubles tennis scheduling problem in the context of a training tournament, and develop a 0–1 mixed-integer programming model that attempts to balance the partnership and the opponentship pairings among the players. We propose effective symmetry-defeating strategies that impose certain decision hierarchies within the model, which serve to significantly enhance algorithmic performance via their pruning effect. We also discuss the concept of symmetry compatible formulations, and highlight the importance of crafting formulations in discrete optimization in a fashion that enhances the interplay between the original model structure, branch-and-bound algorithms (as implemented in commercial packages such as CPLEX), and the structure of specific symmetry-defeating hierarchical constraints. Finally, various specialized heuristics are devised and are computationally evaluated along with the exact solution schemes using a set of realistic practical test problems.

Keywords:

• sports scheduling
• 0–1 mixed-integer programming
• symmetry-defeating constraints
• modelling and optimization

Acknowledgements

This work has been partially supported by the National Science Foundation under grant DMI-0552676. Thanks are also due to an anonymous referee for constructive comments that have greatly helped improve the presentation in this paper. We are also grateful to Dr Patrick Koelling for introducing us to this problem.