×

zbMATH — the first resource for mathematics

Scheduling double round-robin tournaments with divisional play using constraint programming. (English) Zbl 1402.90047
Summary: We study a tournament format that extends a traditional double round-robin format with divisional single round-robin tournaments. Elitserien, the top Swedish handball league, uses such a format for its league schedule. We present a constraint programming model that characterizes the general double round-robin plus divisional single round-robin format. This integrated model allows scheduling to be performed in a single step, as opposed to common multistep approaches that decompose scheduling into smaller problems and possibly miss optimal solutions. In addition to general constraints, we introduce Elitserien-specific requirements for its tournament. These general and league-specific constraints allow us to identify implicit and symmetry-breaking properties that reduce the time to solution from hours to seconds. A scalability study of the number of teams shows that our approach is reasonably fast for even larger league sizes. The experimental evaluation of the integrated approach takes considerably less computational effort to schedule Elitserien than does the previous decomposed approach.

MSC:
90B35 Deterministic scheduling theory in operations research
Software:
Chaff; MiniZinc; STR2
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aho, A. V.; Ullman, J. D., Foundations of computer science, Principles of Computer Science Series, (1994), W. H. Freeman
[2] Beldiceanu, N.; Carlsson, M.; Demassey, S.; Petit, T., Global constraint catalogue: past, present and future, Constraints, 12, 1, 21-62, (2007) · Zbl 1128.68092
[3] Benoist, T.; Laburthe, F.; Rottembourg, B., Lagrange relaxation and constraint programming collaborative schemes for travelling tournament problems, CPAIOR, vol. 1, 15-26, (2001)
[4] Briskorn, D., Sports leagues scheduling, Lecture Notes in Economics and Mathematical Systems: vol. 603, (2008), Springer · Zbl 1133.90003
[5] Cheng, K. C.K.; Yap, R. H.C., An MDD-based generalized arc consistency algorithm for positive and negative table constraints and some global constraints, Constraints, 15, 2, 265-304, (2010) · Zbl 1204.68188
[6] Chu, G.; de la Banda, M. G.; Stuckey, P. J., Automatically exploiting subproblem equivalence in constraint programming, (Lodi, A.; Milano, M.; Toth, P., CPAIOR, LNCS, vol. 6140, (2010), Springer), 71-86 · Zbl 1285.68153
[7] COSYTEC (1997). CHIP reference manual. Release 5.1.
[8] Easton, K.; Nemhauser, G.; Trick, M., The traveling tournament problem description and benchmarks, (Walsh, T., CP, LNCS, vol. 2239, (2001), Springer), 580-584 · Zbl 1067.68627
[9] Focacci, F.; Lodi, A.; Milano, M., Cost-based domain filtering, (Jaffar, J., CP, LNCS, vol. 1713, (1999), Springer), 189-203
[10] Fronček, D.; Meszka, A., Round Robin tournaments with one bye and no breaks in home-away patterns are unique, Multidisciplary scheduling: Theory and applications, 331-340, (2005), Springer · Zbl 1079.90537
[11] Gent, I. P.; Jefferson, C.; Miguel, I.; Nightingale, P., Data structures for generalised arc consistency for extensional constraints, AAAI, 191-197, (2007), AAAI Press
[12] Gent, I. P.; Petrie, K. E.; Puget, J.-F., Symmetry in constraint programming, (Rossi, F.; van Beek, P.; Walsh, T., Handbook of constraint programming chapter 10, (2006), Elsevier New York, NY, USA)
[13] Henz, M., Scheduling a major college basketball conference—revisited, Operations Research, 49, 1, 163-168, (2001) · Zbl 1163.90491
[14] Henz, M.; Müller, T.; Thiel, S., Global constraints for round Robin tournament scheduling, European Journal of Operational Research, 153, 1, 92-101, (2004) · Zbl 1053.90037
[15] Jansson, H. (2016). It’s done: There will now be more matches in the men’s SSL (in Swedish). [Online; posted 2016-03-21]URL: http://innebandymagazinet.se/IBM/artikel.asp?aid=60376.
[16] Larson, J.; Johansson, M., Constructing schedules for sports leagues with divisional and round-Robin tournaments, Journal of Quantitative Analysis in Sports, 10, 2, 119-129, (2014)
[17] Larson, J.; Johansson, M.; Carlsson, M., An integrated constraint programming approach to scheduling sports leagues with divisional and round-Robin tournaments, (Simonis, H., CPAIOR, LNCS, vol. 8451, (2014), Springer), 144-158 · Zbl 06298789
[18] Lecoutre, C., STR2: optimized simple tabular reduction for table constraints, Constraints, 16, 4, 341-371, (2011) · Zbl 1244.90232
[19] Lecoutre, C.; Likitvivatanavong, C.; Yap, R. H.C., STR3: A path-optimal filtering algorithm for table constraints, Artificial Intelligence, 220, 1-27, (2015) · Zbl 1328.68199
[20] Lecoutre, C.; Szymanek, R., Generalized arc consistency for positive table constraints, (Benhamou, F., CP, LNCS, vol. 4204, (2006), Springer), 284-298 · Zbl 1335.90096
[21] Moskewicz, M. W.; Madigan, C. F.; Zhao, Y.; Zhang, L.; Malik, S., Chaff: engineering an efficient SAT solver, Design automation conference, 530-535, (2001), ACM
[22] Nethercote, N.; Stuckey, P. J.; Becket, R.; Brand, S.; Duck, G. J.; Tack, G., Minizinc: towards a standard CP modelling language, (Bessiere, C., CP, LNCS, vol. 4741, (2007), Springer), 529-543
[23] Ohrimenko, O.; Stuckey, P.; Codish, M., Propagation = lazy clause generation, (Bessiere, C., CP, LNCS, vol. 4741, (2007), Springer), 544-558 · Zbl 1145.68527
[24] Perron, L., Alternate modeling in sport scheduling, (van Beek, P., CP, LNCS, vol. 3709, (2005), Springer), 797-801
[25] Pesant, G., A regular language membership constraint for finite sequences of variables, (Wallace, M., CP, LNCS, vol. 3258, (2004), Springer), 482-495 · Zbl 1152.68573
[26] Rasmussen, R., Scheduling a triple round Robin tournament for the best danish soccer league, European Journal of Operational Research, 185, 795-810, (2008) · Zbl 1137.90513
[27] Rasmussen, R. V.; Trick, M. A., The timetable constrained distance minimization problem, (Beck, J. C.; Smith, B., CPAIOR, LNCS, vol. 3990, (2006), Springer), 167-181 · Zbl 1177.90180
[28] Rasmussen, R. V.; Trick, M. A., A benders approach for the constrained minimum break problem, European Journal of Operational Research, 177, 1, 198-213, (2007) · Zbl 1102.90026
[29] Rasmussen, R. V.; Trick, M. A., Round Robin scheduling—a survey, European Journal of Operational Research, 188, 3, 617-636, (2008) · Zbl 1144.90396
[30] Régin, J.-C., A filtering algorithm for constraints of difference in csps, AAAI, 362-367, (1994), AAAI Press
[31] Régin, J.-C., Generalized arc consistency for global cardinality constraint, AAAI, 209-215, (1996), AAAI Press
[32] Régin, J.-C., The symmetric alldiff constraint, (Dean, T., IJCAI, (1999), Morgan Kaufmann), 420-425, http://ijcai.org/Proceedings/99-1/Papers/061.pdf
[33] Régin, J.-C., Minimization of the number of breaks in sports scheduling problems using constraint programming, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 57, 115-130, (2001) · Zbl 0983.90055
[34] (Rossi, F.; van Beek, P.; Walsh, T., (2006), Elsevier New York, NY, USA)
[35] Russell, R. A.; Urban, T. L., A constraint programming approach to the multiple-venue, sport-scheduling problem, Computers & Operations Research, 33, 7, 1895-1906, (2006) · Zbl 1090.90093
[36] Schaerf, A., Scheduling sport tournaments using constraint logic programming, Constraints, 4, 1, 43-65, (1999) · Zbl 0949.90045
[37] Schulte, C.; Tack, G., Modeling and programming with gecode, (2014)
[38] Smith, B., Modelling, (Rossi, F.; van Beek, P.; Walsh, T., Handbook of constraint programming chapter 11, (2006), Elsevier New York, NY, USA)
[39] Trick, M. A., A schedule-then-break approach to sports timetabling, (Burke, E. K.; Erben, W., PATAT, LNCS, vol. 2079, (2000), Springer), 242-253 · Zbl 0982.68531
[40] Trick, M. A., Integer and constraint programming approaches for round Robin tournament scheduling, (Burke, E. K.; Causmaecker, P. D., PATAT, LNCS, vol. 2740, (2002), Springer), 63-77
[41] van Hoeve, W.-J.; Katriel, I., Global constraints, (Rossi, F.; van Beek, P.; Walsh, T., Handbook of constraint programming chapter 6, (2006), Elsevier New York, NY, USA)
[42] van’t Hof, P.; Post, G.; Briskorn, D., Constructing fair round-Robin tournaments with a minimum number of breaks, Operations Research Letters, 38, 592-596, (2010) · Zbl 1202.90151
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.