BL.Optim es un proyecto de investigación de Berger-Levrault sobre la gestión de la planificación mediante un algoritmo de optimización. Sin embargo, la parte de "descripción de restricciones" en BL.Optim se apoya en una API, que es extremadamente difícil de utilizar para expresar nuevas restricciones. Queremos sustituir el descriptor de restricciones por un lenguaje más o menos expresivo, que nos permita adaptar fácilmente nuestra implementación a otros problemas basados en reglas en los distintos ámbitos. El problema en cuestión es el problema de optimización basado en la programación de satisfacción de restricciones (CSP).
Trabajamos en la formulación y resolución de problemas de optimización utilizando un lenguaje específico del dominio (DSL). Antes de hablar de los lenguajes de modelado existentes y sus características, hablaremos de CSP, que es un enfoque alternativo de la programación matemática, que combina el razonamiento y los cálculos. El problema de optimización basado en CSP se compone de dos partes: el modelado y la resolución.
¿Cómo traducir el problema de optimización de la vida real al campo de las matemáticas aplicadas para obtener una solución de apoyo a la toma de decisiones? Al principio, tenemos un problema descrito por el cliente en su lengua materna. Luego lo traducimos a través de la (modelado) proceso para obtener un problema matemático que incluya variables de decisión y restricciones en un dominio preciso. Por último, en el (resolución) parte, el modelo se escribe mediante el uso de DSL. Obtenemos la solución de nuestro problema sometiendo el modelo formulado a un solucionador orientado a CSP.
La figura 1 es un esquema representativo del proceso de generación de soluciones para un problema de optimización:
El estudio realizado
Impulsamos la investigación sobre las dos partes del problema de optimización basado en CSP, y especialmente la parte de modelado. Como dijimos antes, necesitamos un DSL para realizar el modelado matemático, y encontramos más de 20 DSLs existentes en pleno desarrollo con una rica documentación. Nos interesan los 11 DSLs más citados en la literatura que son: "IBM-ILOG-OPL", "Doceplex", "Py-Constraint", "OptaPlanner", "OR-Tools", "EacL", "MiniZinc", "JuMP", "PyCsp3", "Picat" y "JvCSP3". Los separamos en dos categorías:
- la primera categoría se refiere al DSL que está incrustado en un solucionador, como se muestra en el escenario 1 de la Figura 2, la llamada al solucionador se hace directamente después de la compilación de las instancias de datos y el modelo.
- Para la segunda categoría, como se muestra en el escenario 2 de la Figura 2, se obtiene un archivo intermedio como resultado de la compilación del modelo CSP. Este archivo contiene los modelos sin la solución, y la llamada al solucionador se hace después, por separado con la parte de modelado mediante el uso de DSL. Por ejemplo, para "MiniZinc", tenemos un "FlatZinc" como archivo intermedio. Para "PyCSP3", un "XCSP3" es el resultado de la compilación del modelo escrito en "XCSP3".
Como parte de este proyecto de investigación, nos interesa más el segundo escenario porque es el que nos permitirá hacer el cambio en el modelo sin tener que cambiar todo el funcionamiento de la resolución. Además, nos permitirá resolver el modelo utilizando un solver diferente.
Para una mejor comprensión de los dos escenarios, los esquematizamos como sigue:
El Problema de Programación y Rutas de Mantenimiento Preventivo (PMSRP) es elegido como caso de uso para el propósito de la experimentación. Comenzamos el modelado del PMSRP [1] con "MiniZinc" porque es ampliamente utilizado en la literatura para resolver el problema formulado basado en CSP. Después de compilar el modelo escrito en DSL "MiniZinc", obtenemos un archivo aplanado "FlatZinc". Además, podemos escribir restricciones complejas porque al compilar el modelo, el compilador de "MiniZinc" aplana las restricciones en el fichero de salida intermedio. El inconveniente que hemos encontrado hasta ahora con este DSL, es que los solucionadores propuestos por el IDE de "MiniZinc" se basan en el método exacto. Para resolver nuestro problema con complejidad NP-completa, el experimento muestra que podemos resolver un problema de hasta 50 actividades de mantenimiento por día, los solucionadores integrados en el IDE de "MiniZinc" (Cf. Figura 3 - IDE "MiniZinc") no pueden darnos una solución en un tiempo de cálculo razonable (≥3 horas).
Obras futuras
En un futuro próximo, haremos un experimento completo con "MiniZinc", utilizando conjuntos de datos reales para poder probarlos con diferentes solucionadores. A continuación, compararemos la calidad de las soluciones generadas por los diferentes solucionadores con sus prestaciones informáticas. Por último, investigaremos la posibilidad de integrar el DSL "MiniZinc" en BL.Optim, lo que nos ayudará a mejorar la ineficiencia en la formulación de nuevas reglas de negocio en diversos contextos.
Por Sihem Laradi
