Modelos y técnicas de consistencia en problemas de satisfacción de restricciones

• Autores: Marlene Alicia Arangú Lobig
• Directores de la Tesis: Miguel Angel Salido Gregorio (dir. tes.)
• Lectura: En la Universitat Politècnica de València ( España ) en 2011
• Idioma: español
• Tribunal Calificador de la Tesis: Federico Barber Sanchís (presid.) , María Camino Rodríguez Vela (secret.) , Juan Fernández Olivares (voc.) , José Ramiro Varela Arias (voc.) , Carmelo del Valle Sevillano (voc.)
• Enlaces
  • Tesis en acceso abierto en: TESEO
• Resumen

  • Hoy en día, muchos problemas reales pueden ser modelados como problemas de satisfacción de restricciones (CSPs) y ser resueltos utilizando técnicas de programación de restricciones. Estos problemas pertenecen a diferentes áreas de conocimiento tales como inteligencia artificial, investigación operativa, sistemas de información, bases de datos, etc. Los CSPs pertenecen a la categoría de problemas NP-completos por lo que es necesario el uso de herramientas que simplifiquen el problema de forma que se encuentre una solución de forma eficiente. Las técnicas más comunes para manejar un CSP son las técnicas de consistencia y las técnicas de búsqueda. Las técnicas de consistencia o de filtrado tienen por objeto reducir el espacio de búsqueda mediante el filtrado de los dominios de las variables. Las técnicas de arco-consistencia son las más utilizadas ya que llevan a cabo una importante poda de dominios; eliminando valores que no formaran parte de la solución; de una manera eficiente.

    Por ello, proponer algoritmos que alcancen la arco-consistencia ha sido un punto central en la comunidad científica reduciendo la complejidad tanto espacial como temporal de estos algoritmos.

    Sin embargo, muchos trabajos que investigan la arco-consistencia llevan a cabo asunciones que no están presentes en muchos problemas de la vida real. Por ejemplo, un mismo par de variables puede participar en más de una restricción, lo que se denomina problema no-normalizado, y cuando el tamaño de los dominios es grande, el proceso de normalización puede resultar prohibitivo. En estos casos la 2-consistencia lleva a cabo una reducción de los dominios de las variables mayor que la arco-consistencia por lo que los algoritmos de búsqueda pueden resultar más eficientes. No obstante, la literatura es escasa en relación al desarrollo de algoritmos que alcancen la 2-consistencia.

    En esta tesis presentamos nuevos algoritmos de arco-consistencia y de 2-consistencia como algoritmos de preproceso para la resolución de problemas de satisfacción de restricciones. Estos algoritmos presentan un mejor comportamiento que las actuales técnicas existentes en la literatura en algunos de los criterios de eficiencia establecidos por la comunidad científica: reducción del número de chequeos de restricciones, reducción de la cantidad de propagaciones, disminución del tiempo de cómputo, o el aumento de la cantidad de poda. En este trabajo también presentamos un algoritmo de normalización híbrido, que permite calcular el coste del proceso de normalización requerido para aplicar las técnicas existentes en la literatura. En cuanto a las técnicas de búsqueda, en esta tesis presentamos dos algoritmos: un algoritmo heurístico de propósito general y un algoritmo completo y dependiente del dominio. Ambos algoritmos se benefician de los resultados proporcionados por las técnicas de 2-consistencia desarrolladas en esta tesis. Adicionalmente y debido a que muchos problemas reales pueden modelarse de forma natural mediante el uso de restricciones no-binarias, en esta tesis proponemos un lenguaje de modelado que combina el uso de CSPs con restricciones no-binarias y planificación POCL para problemas de planificación y scheduling. El lenguaje de modelado propuesto permite codificar restricciones complejas, expresar el uso de los recursos continuos y beneficiarse de las técnicas de consistencia desarrolladas en esta tesis.

    Todas las técnicas presentadas se han evaluado empíricamente sobre diferentes instancias de problemas aleatorios y benchmarks. También han sido aplicadas a la resolución del problema de planificación de horarios ferroviarios.