Improving the solving efficiency of TOY (FD) and its application to real-life problems
Ignacio Castiñeíras Pérez · 2014
El area de conocimiento de la programacion con restricciones sobre dominios ?nitos (CP(FD)) ha sido identi?cada como especialmente adecuada para el modelado y resolucion de problemas de satisfaccion y optimizacion 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), programacion logica con restricciones (CLP(FD)) y programacion logico 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 investigacion en tres partes: una mejora del rendimiento de TOY(FD), una descripcion 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 investigacion mejora el rendimiento de resolucion de TOY(FD). En concreto, se desarrolla un esquema generico 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 busqueda. Estas permiten una mejor especi?cacion de estrategias de busqueda ad hoc, que explotan la estructura del problema a resolver, precisando una menor exploracion de busqueda para computar las soluciones del mismo.La segunda parte de la investigacion presenta dos aplicaciones industriales del sistema TOY(FD). La primera es un problema de asignacion de trabajadores a turnos de trabajo, proveniente de la industria de las comunicaciones, y modelado y resuelto con TOY(FD). La segunda es un analisis empirico de la complejidad del problema de asignacion de elementos unidimensionales a contenedores. En este analisis se utilizan tanto tecnicas heuristicas como CP(FD) (esta ultima 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 optimizacion en centros de datos.La tercera parte de la investigacion utiliza el problema de asignacion de trabajadores a turnos de trabajo para realizar una comparativa en profundidad de su modelado y resolucion 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:Programacion con restricciones sobre dominios ?nitos, programacion logico funcional con restricciones, integracion de resolutores de restricciones, estrategias de busqueda, problema de asignacion de trabajadores a turnos de trabajo, problema de asignacion de elementos unidimensionales a contenedores, generacion parametrica de casos de prueba, programacion con restricciones algebraica, programacion con restricciones orientada a objetos, programacion logica con restricciones.