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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Abel RJR, Finizio NJ, Greig M and Lewis SJ (2003). Generalized whist tournament designs . Disc Math 268: 1–19.
Anderson I (1997). Combinatorial Designs and Tournaments . Oxford University Press: Oxford.
Bean J and Birge J (1980). Reducing traveling costs and player fatigue in the National Basketball Association . Interfaces 10(3): 98–102.
Carter M and Guthrie G (2004). Cricket interruptus: Fairness and incentive in limited overs cricket matches . J Opl Res Soc 55: 822–829.
Costa D (1995). An evolutionary tabu search algorithm and the NHL scheduling problem . INFOR 33: 161–178.
Della Croce F, Tadei R and Asioli PS (1999). Scheduling a round robin tennis tournament under courts and players availability constraints . Ann of Opns Res 92: 349–361.
de Werra D (1980). Geography, games, and graphs . Disc Appl Math 2: 327–337.
de Werra D (1981). Scheduling in sports . In: Hansen P (ed). Studies on Graphs and Discrete Programming. North-Holland: Amsterdam, pp. 381–395.
de Werra D (1985). On the multiplication of divisions: The use of graphs for sports scheduling . Networks 15: 125–136.
Duckworth FC and Lewis AJ (1998). A fair method for resetting the target in interrupted one-day cricket matches . J Opl Res Soc 49: 220–227.
Ferland JA and Fleurent C (1991). Computer aided scheduling of a sports league . INFOR 29: 14–24.
Ghoniem A (2007). Enhanced formulations for minimax and discrete optimization problems with applications to scheduling and routing. PhD thesis, Department of Industrial and Systems Engineering, Virginia Polytechnic Institute and State University, VA.
Goemans MX and Williamson DP (1995). Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming . J ACM 42: 1115–1145.
Hamiez J-P and Hao J-K (2001). Solving the sports league scheduling problem with tabu search . In: Nareyek A (ed). Lecture Notes in Computer Science Vol. 2148. Springer: Berlin, pp. 24–36.
Henz M (2001). Scheduling a major college basketball conference—Revisited . Opns Res 49: 163–168.
Hurley WJ (2006). Special issue on operations research in sport . Comput Opns Res 33: 1871–1873.
Kendall G (2008). Scheduling English football fixtures over holiday periods . J Opl Res Soc 59: 743–755.
Nemhauser G and Trick M (1998). Scheduling a major college basketball conference . Opns Res 46: 1–8.
Sherali HD and Smith JC (2001). Improving discrete model representations via symmetry considerations . Mngt Sci 47: 1396–1407.
Schonberger J, Mattfeld DC and Kopfer H (2004). Memetic algorithm timetabling for noncommercial sport leagues . Eur J Opl Res 153: 102–116.
Schreuder J (1992). Combinatorial aspects of construction of competition Dutch professional football leagues . Disc Appl Math 35: 301–312.
Suzuka A, Miyashiro R, Yoshise A and Matsui T (2005). Semidefinite programming based approaches to home-away assignment problems in sports scheduling . In: Megiddo N, Xu Y and Zhu B (eds). Lecture Notes in Computer Science Vol. 3521. Springer: Berlin, pp. 95–103.
Trick MA (2003). Integer and constraint programming approaches for round-robin tournament scheduling . In: Burke E and De Causmaecker P (eds). PATAT 2002, Lecture Notes in Computer Science Vol. 2740. Springer: Berlin, pp. 63–77.
Williams HP (1999). Model Building in Mathematical Programming . John Wiley & Sons Ltd: West Sussex, England.
Willis RJ and Terrill BJ (1994). Scheduling the Australian state cricket season using simulated annealing . J Opl Res Soc 45: 276–280.
Wright MB (1991). Scheduling English cricket umpires . J Opl Res Soc 42: 447–452.
Wright MB (2007). Case study: Problem formulation and solution for a real-world sports scheduling problem . J Opl Res Soc 58: 439–445.
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.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Ghoniem, A., Sherali, H. Models and algorithms for the scheduling of a doubles tennis training tournament. J Oper Res Soc 61, 723–731 (2010). https://doi.org/10.1057/jors.2008.190
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1057/jors.2008.190