|
Título:
|
Generating Hard Satisfiable Scheduling Instances
|
|
Autor/a:
|
Argelich Romà, Josep; Béjar Torres, Ramón; Cabiscol i Teixidó, Alba; Fernàndez Camon, César; Manyà Serres, Felip; Gomes, Carla
|
|
Notas:
|
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
Research partially funded by the Generalitat de Catalunya under grant AGAUR 2009-SGR-1434, the Ministerio de EconomÍa y Competividad research projects AT CONSOLIDER CSD2007-0022, INGENIO 2010, ARINF TIN2009-14704-C03-01, TASSAT TIN2010- 20967-C04-01/03, and Newmatica INNPACTO IPT-2011-1496-310000 (funded by the Ministerio de Ciencia y Tecnología until 2011). |
|
Materia(s):
|
-Satisfiability
-Benchmarks
-Local Search |
|
Derechos:
|
(c) Association for the Advancement of Artificial Intelligence (AAAI), 2013
|
|
Tipo de documento:
|
conferenceObject
acceptedVersion |
|
Editor:
|
European Conference on Planning
|
|
Compartir:
|
|
