Constraint programming for high school timetabling: a scheduling-based model with hot starts

Emir Demirović, Peter J. Stuckey

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

1 Citation (Scopus)

Abstract

High School Timetabling (HSTT) is a well-known and wide-spread problem. It consists of coordinating resources (e.g. teachers, rooms), times, and events (e.g. classes) with respect to a variety of constraints. In this paper, we study the applicability of constraint programming (CP) for high school timetabling. We formulate a novel CP model for HSTT using a scheduling-based point of view. We show that a drastic improvement in performance over the baseline CP model can be achieved by including solution-based phase saving, which directs the CP solver to first search in close proximity to the best solution found, and our hot start approach, where we use existing heuristic methods to produce a starting point for the CP solver. The experiments demonstrate that our approach outperforms the IP and maxSAT complete methods and provides competitive results when compared to dedicated heuristic solvers.

Original languageEnglish
Title of host publicationIntegration of Constraint Programming, Artificial Intelligence, and Operations Research
Subtitle of host publication15th International Conference, CPAIOR 2018 Delft, The Netherlands, June 26–29, 2018 Proceedings
EditorsWillem-Jan van Hoeve
Place of PublicationCham Switzerland
PublisherSpringer
Pages135-152
Number of pages18
ISBN (Electronic)9783319930312
ISBN (Print)9783319930305
DOIs
Publication statusPublished - 2018
Externally publishedYes
EventInternational Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems 2018 - Delft, Netherlands
Duration: 26 Jun 201829 Jun 2018
Conference number: 15th
https://sites.google.com/view/cpaior2018

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume10848
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceInternational Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems 2018
Abbreviated titleCPAIOR 2018
CountryNetherlands
CityDelft
Period26/06/1829/06/18
Internet address

Keywords

  • Constraint programming
  • Hot start
  • Local search
  • Modeling
  • Phase saving
  • Scheduling
  • Timetabling
  • Warm start

Cite this

Demirović, E., & Stuckey, P. J. (2018). Constraint programming for high school timetabling: a scheduling-based model with hot starts. In W-J. van Hoeve (Ed.), Integration of Constraint Programming, Artificial Intelligence, and Operations Research: 15th International Conference, CPAIOR 2018 Delft, The Netherlands, June 26–29, 2018 Proceedings (pp. 135-152). (Lecture Notes in Computer Science ; Vol. 10848 ). Springer. https://doi.org/10.1007/978-3-319-93031-2_10