AAAI Publications, Sixth European Conference on Planning

Font Size: 
Generating Hard Satisfiable Scheduling Instances
Josep Argelich, Ramón Béjar, Alba Cabiscol, Cèsar Fernández, Felip Manyà, Carla Gomes

Last modified: 2014-05-21

Abstract


We present a random generator of partially complete round robin timetables that produces exclusively satisfiable instances, and provide experimental evidence that there is an easy-hard-easy pattern in the computational difficulty of completing partially complete timetables as the ratio of the number of removed entries to the total number of entries of the timetable is varied. Timetables in the hard region provide a suitable test-bed for evaluating and fine-tuning local search algorithms.

Keywords


Satisfiability; Benchmarks; Local Search

Full Text: PDF