Improving the solving efficiency of TOY (FD) and its application to real-life problems

Resumen

El área de conocimiento de la programación con restricciones sobre dominios ¿nitos (CP(FD)) ha sido identi¿cada como especialmente adecuada para el modelado y resolución de problemas de satisfacción y optimización de restriccciones (CSP y COP, respectivamente), ya que captura su naturaleza orientada a restricciones de una manera concisa. Dentro de CP(FD), los cuatro paradigmas CP(FD) algebraico, C++ CP(FD), programación lógica con restricciones (CLP(FD)) y programación lógico funcional con restricciones (CFLP(FD)) se basan en un resolutor de restricciones, pero di¿eren en el lenguaje de modelado utilizado. En particular, CFLP(FD) ofrece lenguajes altamente expresivos y, sin embargo, la literatura carece de tantas aplicaciones como las existentes para CP(FD) algebraico, C++ CP(FD) y CLP(FD).El objetivo principal de esta tesis es fomentar el uso de CFLP(FD) para hacer frente a CSP y COP de la vida real. Para ello, se ha seleccionado al sistema TOY(FD) (perteneciente al paradigma CFLP(FD)), y se ha dividido a la investigación en tres partes: una mejora del rendimiento de TOY(FD), una descripción de aplicaciones industriales para TOY(FD) y un posicionamiento de TOY(FD) con respecto a sistemas de vanguardia CP(FD) algebraicos, C++ CP(FD) y CLP(FD).La primera parte de la investigación mejora el rendimiento de resolución de TOY(FD). En concreto, se desarrolla un esquema genérico para integrar resolutores C++ CP(FD) en TOY(FD), y se implementan dos nuevas versiones del sistema que resultan de instanciar el esquema con Gecode e ILOG Solver. Asimismo, se aumenta la capacidad expresiva de TOY(FD) con nuevas primitivas de búsqueda. Estas permiten una mejor especi¿cación de estrategias de búsqueda ad hoc, que explotan la estructura del problema a resolver, precisando una menor exploración de búsqueda para computar las soluciones del mismo.La segunda parte de la investigación presenta dos aplicaciones industriales del sistema TOY(FD). La primera es un problema de asignación de trabajadores a turnos de trabajo, proveniente de la industria de las comunicaciones, y modelado y resuelto con TOY(FD). La segunda es un análisis empírico de la complejidad del problema de asignación de elementos unidimensionales a contenedores. En este análisis se utilizan tanto técnicas heurísticas como CP(FD) (esta última incluyendo a TOY(FD)) para resolver un conjunto de casos de prueba, que resulta representativo de instancias generalizadas del problema provenientes de la industria de la optimización en centros de datos.La tercera parte de la investigación utiliza el problema de asignación de trabajadores a turnos de trabajo para realizar una comparativa en profundidad de su modelado y resolución en diferentes sistemas CP(FD) de vanguardia. En concreto, se seleccionan los sistemas CP(FD) algebraicos Minizinc e ILOG OPL, los sistemas C++ CP(FD) Gecode e ILOG Solver, los sistemas CLP(FD) SICStus Prolog y SWI-Prolog, y los sistemas CFLP(FD) PAKCS y TOY(FD). La comparativa muestra que TOY(FD) es competitivo con respecto a cualquiera de los otros sistemas.Palabras clave de la tesis doctoral:Programación con restricciones sobre dominios ¿nitos, programación lógico funcional con restricciones, integración de resolutores de restricciones, estrategias de búsqueda, problema de asignación de trabajadores a turnos de trabajo, problema de asignación de elementos unidimensionales a contenedores, generación paramétrica de casos de prueba, programación con restricciones algebraica, programación con restricciones orientada a objetos, programación lógica con restricciones.