Feature-based tuning of single-stage simulated annealing for examination timetabling.

*(English)*Zbl 1368.90060Summary: We propose a simulated annealing approach for the examination timetabling problem, as formulated in the 2nd International Timetabling Competition. We apply a single-stage procedure in which infeasible solutions are included in the search space and dealt with using suitable penalties. Upon our approach, we perform a statistically-principled experimental analysis, in order to understand the effect of parameter selection on the performance of our algorithm, and to devise a feature-based parameter tuning strategy, which can achieve better generalization on unseen instances with respect to a one-fits-all parameter setting. The outcome of this work is that this rather straightforward search method, if properly tuned, is able to compete with all state-of-the-art specialized solvers on the available instances. As a byproduct of this analysis, we propose and publish a new, larger set of (artificial) instances that could be used for tuning and also as a ground for future comparisons.

##### MSC:

90B35 | Deterministic scheduling theory in operations research |

90C59 | Approximation methods and heuristics in mathematical programming |

##### Keywords:

examination timetabling; local search; simulated annealing; metaheuristics; linear regression; feature-based parameter tuning
PDF
BibTeX
XML
Cite

\textit{M. Battistutta} et al., Ann. Oper. Res. 252, No. 2, 239--254 (2017; Zbl 1368.90060)

Full Text:
DOI

##### References:

[1] | Abramson, D, Constructing school timetables using simulated annealing: sequential and parallel algorithms, Management Science, 37, 98-113, (1991) |

[2] | Alzaqebah, M; Abdullah, S, An adaptive artificial bee colony and late-acceptance Hill-climbing algorithm for examination timetabling, Journal of Scheduling, 17, 249-262, (2014) · Zbl 1297.90181 |

[3] | Alzaqebah, M; Abdullah, S, Hybrid bee colony optimization for examination timetabling problems, Computers and Operations Research, 54, 142-154, (2015) · Zbl 1348.90238 |

[4] | Bellio, R; Ceschia, S; Gaspero, L; Schaerf, A; Urli, T, Feature-based tuning of simulated annealing applied to the curriculum-based course timetabling problem, Computers & Operations Research, 65, 83-92, (2016) · Zbl 1349.90316 |

[5] | Bellio, R; Gaspero, L; Schaerf, A, Design and statistical analysis of a hybrid local search algorithm for course timetabling, Journal of Scheduling, 15, 49-61, (2012) |

[6] | Birattari, M., Yuan, Z., Balaprakash, P., & Stützle, T. (2010). F-race and iterated F-race: An overview. In Th. Bartz-Beielstein, M. Chiarandini, M. Paquete, & M. Preuss (Eds.), Experimental methods for the analysis of optimization algorithms (pp. 311-336). Springer: Berlin. · Zbl 1204.68280 |

[7] | Burke, EK; Qu, R; Soghier, A, Adaptive selection of heuristics for improving exam timetables, Annals of Operations Research, 218, 129-145, (2014) · Zbl 1301.90031 |

[8] | Bykov, Y., & Petrovic, S. (2013). An initial study of a novel step counting hill climbing heuristic applied to timetabling problems. In Proceedings of the 6th multidisciplinary international conference on scheduling: Theory and applications (MISTA-13) (pp. 691-693). · Zbl 1291.90326 |

[9] | Carter, MW, A survey of practical applications of examination timetabling algorithms, Operations Research, 34, 193-202, (1986) |

[10] | Carter, M.W., & Laporte, G. (1996). Recent developments in pratical examination timetabling. In Burke, E. K., Ross, P. (Ed.), Proceedings of the 1st international conference on the practice and theory of automated timetabling (ICPTAT-95). Lecture notes in computer science (Vol. 1153, pp. 3-21). Berlin: Springer. |

[11] | Carter, MW; Laporte, G; Lee, SY, Examination timetabling: algorithmic strategies and applications, Journal of the Operational Research Society, 74, 373-383, (1996) |

[12] | Ceschia, S; Gaspero, L; Schaerf, A, Design, engineering, and experimental analysis of a simulated annealing approach to the post-enrolment course timetabling problem, Computers & Operations Research, 39, 1615-1624, (2012) |

[13] | Di Gaspero, L., & Schaerf, A. (2003). EasyLocal++: An object-oriented framework for flexible design of local search algorithms. Software-Practice and Experience, 33(8), 733-765. |

[14] | Dowsland, KA, A timetabling problem in which clashes are inevitable, Journal of the Operational Research Society, 41, 907-918, (1990) |

[15] | Glover, F., & Laguna, M. (1997). Tabu search. London: Kluwer Academic Publishers. · Zbl 0930.90083 |

[16] | Gogos, C; Alefragis, P; Housos, E, An improved multi-staged algorithmic process for the solution of the examination timetabling problem, Annals of Operations Research, 194, 203-221, (2012) · Zbl 1251.90149 |

[17] | Gogos, C., Goulas, G., Alefragis, P., Kolonias, V., & Housos, E. (2010). Distributed scatter search for the examination timetabling problem. In Proceedings of the 8th international conference on the practice and theory of automated timetabling (PATAT-2010) (pp. 211-223). |

[18] | Hamilton-Bryce, R., McMullan, P., & McCollum, B. (2013). Directing selection within an extended great deluge optimization algorithm. In Proceedings of the 6th multidisciplinary international conference on scheduling: Theory and applications (MISTA-13) (pp. 499-508). |

[19] | Hammersley, JM; Handscomb, DC; Weiss, G, Monte Carlo methods, Physics Today, 18, 55, (1965) |

[20] | Johnson, DS; Aragon, CR; McGeoch, LA; Schevon, C, Optimization by simulated annealing: an experimental evaluation; part I, graph partitioning, Operations Research, 37, 865-892, (1989) · Zbl 0698.90065 |

[21] | Jolliffe, I. (2005). Principal component analysis. Hoboken: Wiley Online Library. · Zbl 1011.62064 |

[22] | Koenker, R. (2005). Quantile regression. Cambridge: Cambridge University Press. · Zbl 1111.62037 |

[23] | Lopes, L., & Smith-Miles, K. (2010). Pitfalls in instance generation for Udine timetabling. In C. Blum, & R. Battiti (Eds.), Learning and intelligent optimization (LION4) (pp. 299-302). Berlin: Springer. · Zbl 0851.90069 |

[24] | Mascia, F; Pellegrini, P; Birattari, M; Stützle, T, An analysis of parameter adaptation in reactive tabu search, International Transactions in Operational Research, 21, 127-152, (2014) · Zbl 1291.90326 |

[25] | McCollum, B., McMullan, P. J., Parkes, A. J., Burke, E. K., & Abdullah, S. (2009). An extended great deluge approach to the examination timetabling problem. In Proceedings of the 4th multidisciplinary international conference on scheduling: Theory and applications (MISTA-09) (pp. 424-434). |

[26] | McCollum, B. (2007). A perspective on bridging the gap in university timetabling. In E. Burke & H. Rudová (Eds.), Proceedings of the 6th international conference on the practice and theory of automated timetabling (PATAT-2006), selected papers. Lecture notes in computer science, (Vol. 3867, pp. 3-23). Berlin: Springer. · Zbl 1349.90316 |

[27] | McCollum, B., McMullan, P., Burke, E. K., Parkes, A. J., & Qu, R. (2007). The second international timetabling competition: Examination timetabling track. Technical report QUB/IEEE/Tech/ITC2007/Exam/v4.0/17, Queen’s University, Belfast (UK), September. · Zbl 1243.90007 |

[28] | McCollum, B; Schaerf, A; Paechter, B; McMullan, P; Lewis, R; Parkes, AJ; Gaspero, L; Rong, Q; Burke, EK, Setting the research agenda in automated timetabling: the second international timetabling competition, INFORMS Journal on Computing, 22, 120-130, (2010) · Zbl 1243.90007 |

[29] | Merlot, L., Boland, N., Hughes, B., & Stuckey, P. (2003). A hybrid algorithm for the examination timetabling problem. In B. Edmund & C. Patrick De (Eds.) Proceedings of the 4th international conference on the practice and theory of automated timetabling (PATAT-2002), selected papers. Lecture notes in computer science (Vol. 2740, pp. 207-231). Berlin: Springer. · Zbl 1301.90031 |

[30] | Müller, T, ITC2007 solver description: A hybrid approach, Annals of Operations Research, 172, 429-446, (2009) · Zbl 1184.90143 |

[31] | Nethercote, N., Stuckey, P. J., Becket, R., Brand, S., Duck, G. J., & Tack, G. (2007). MiniZinc: Towards a standard CP modelling language. In C. Bessière (Ed.), Principles and practice of constraint programming CP 2007 (pp. 529-543). Berlin: Springer. |

[32] | Özcan, E., Elhag, A., & Shah, V. (2012). A study of hyper-heuristics for examination timetabling. In Proceedings of the 9th international conference on the practice and theory of automated timetabling (PATAT-2012) (pp. 410-414). · Zbl 1042.90568 |

[33] | Pillay, N. (2010). Evolving hyper-heuristics for a highly constrained examination timetabling problem. In Proceedings of the 8th international conference on the practice and theory of automated timetabling (PATAT-2010) (pp. 211-223). |

[34] | Qu, R; Burke, E; McCollum, B; Merlot, L; Lee, SY, A survey of search methodologies and automated system development for examination timetabling, Journal of Scheduling, 12, 55-89, (2009) · Zbl 1279.90071 |

[35] | R Development Core Team (2008). R: A language and environment for statistical computing. Vienna, Austria: R Foundation for Statistical Computing. |

[36] | Sabar, NR; Ayob, M; Kendall, G; Qu, R, A dynamic multiarmed bandit-gene expression programming hyper-heuristic for combinatorial optimization problems, IEEE Transactions on Cybernetics, 45, 217-228, (2014) |

[37] | Schaerf, A, A survey of automated timetabling, Artificial Intelligence Review, 13, 87-127, (1999) |

[38] | Smith-Miles, K. A., & Lopes, L. (2011). Generalising algorithm performance in instance space: A timetabling case study. In C. A. Coello Coello (Ed.), Learning and intelligent optimization (LION 2011). Lecture notes in computer science (Vol. 6683, pp. 524-538). Springer: Berlin. |

[39] | Thompson , JM; Dowsland, KA, Variants of simulated annealing for the examination timetabling problem, Annals of Operations Research, 63, 105-128, (1996) · Zbl 0851.90069 |

[40] | Thompson, JM; Dowsland, KA, A robust simulated annealing based examination timetabling system, Computers and Operations Research, 25, 637-648, (1998) · Zbl 1042.90568 |

[41] | Urli, T. (2013). json2run: A tool for experiment design & analysis. CoRR, arXiv:abs/1305.1112. · Zbl 1243.90007 |

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.