Pasar al contenido principal

TEORIA, APLICACIONES Y SINERGIA EN SAT, CSP Y FDL

TIN2010-20967-C04-03

•
Nombre agencia financiadora Ministerio de Ciencia e Innovación
Acrónimo agencia financiadora MICINN
Programa Programa Nacional de Proyectos de Investigación Fundamental
Subprograma Subprograma de Proyectos de Investigación Fundamental no Orientada
Convocatoria Proyectos I+D
Año convocatoria 2010
Plan Estatal 2008-2011 Plan Nacional de Investigación Científica, Desarrollo e Innovación Tecnológica
Unidad de gestión Subdirección General de Proyectos de Investigación
Centro beneficiario UNIVERSIDAD DE LLEIDA
Identificador persistente http://dx.doi.org/10.13039/501100004837

Resultados relacionados

Resultados totales (Incluyendo duplicados): 2
Encontrada(s) 1 página(s)

Repositori Obert UdL
Publicación Contribución de congreso (ConferenceOutput)

Generating Hard Satisfiable Scheduling Instances

  • Argelich Romà, Josep
  • Béjar Torres, Ramón
  • Cabiscol i Teixidó, Alba
  • Fernàndez Camon, César
  • Manyà Serres, Felip
  • Gomes, Carla
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).
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Generating Hard Satisfiable Scheduling Instances

  • Argelich Romà, Josep
  • Béjar Torres, Ramón
  • Cabiscol i Teixidó, Alba
  • Fernàndez Camon, César
  • Manyà Serres, Felip
  • Gomes, Carla
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).