Résolution de problèmes d'optimisation par le biais d'un modélisateur de règles de gestion basé sur un langage spécifique au domaine

Partager par e-mail
Langage spécifique au domaine BL.Optim

BL.Optim est un projet de recherche de Berger-Levrault portant sur la gestion de la planification par un algorithme d'optimisation. Cependant, la partie "description des contraintes" dans BL.Optim est supportée par une API, extrêmement difficile à utiliser pour exprimer de nouvelles contraintes. Nous voulons remplacer le descripteur de contraintes en utilisant un langage plus ou moins expressif, qui nous permette d'adapter facilement notre implémentation à d'autres problèmes guidés par des règles dans les différents domaines. Nous nous intéressons plus particulièrement ici au problème d'optimisation basé sur la programmation par satisfaction de contraintes (CSP).

Nous avons travaillé sur la formulation et la résolution de problèmes d'optimisation en utilisant un langage spécifique au domaine (DSL). Avant de parler des langages de modélisation existants et de leurs caractéristiques, nous allons parler de CSP : une approche alternative de la programmation mathématique, combinant raisonnement et calculs. Un problème d'optimisation basé sur CSP est composé de deux parties : la modélisation et la résolution.
Alors comment traduire le problème d'optimisation de la vie réelle dans le domaine des mathématiques appliquées afin d'obtenir une solution d'aide à la décision ? Au départ, nous avons un problème décrit par le client dans sa langue maternelle. Ensuite, nous le traduisons par la (modélisation) pour obtenir un problème mathématique comprenant des variables de décision et des contraintes sur un domaine précis. Enfin, dans la (résolution) Le modèle est écrit à l'aide d'un DSL. Nous obtenons la solution de notre problème en soumettant le modèle formulé à un solveur orienté CSP.
La figure 1 est un schéma représentatif du processus de génération de solutions pour un problème d'optimisation :

Schématisation du CSP pour un problème d'optimisation
Figure 1 : schématisation de la résolution pour un problème d'optimisation basé sur CSP

L'étude menée

Nous avons poussé la recherche sur les deux parties du problème d'optimisation basé sur CSP, et en particulier sur la partie modélisation. Comme nous l'avons dit précédemment, nous avons besoin d'un DSL pour réaliser la modélisation mathématique, et nous avons trouvé plus de 20 DSLs existants en plein développement avec une riche documentation. Nous sommes intéressés par les 11 DSLs les plus cités dans la littérature qui sont : "IBM-ILOG-OPL", "Doceplex", "Py-Constraint", "OptaPlanner", "OR-Tools", "EacL", "MiniZinc", "JuMP", "PyCsp3", "Picat" et "JvCSP3". Nous les avons séparés en deux catégories :

  • la première catégorie fait référence au DSL qui est intégré dans un solveur, comme le montre le scénario 1 de la figure 2, l'appel au solveur se fait directement après la compilation des instances de données et du modèle.
  • Pour la deuxième catégorie, comme le montre le scénario 2 de la figure 2, un fichier intermédiaire est obtenu à la suite de la compilation du modèle CSP. Ce fichier contient les modèles sans la solution, et l'appel au solveur se fait après, séparément de la partie modélisation par l'utilisation du DSL. Par exemple, pour "MiniZinc", nous avons un "FlatZinc". comme fichier intermédiaire. Pour "PyCSP3", un "XCSP3" est le résultat de la compilation du modèle écrit en "XCSP3".

Dans le cadre de ce projet de recherche, nous sommes plus intéressés par le second scénario car c'est celui qui nous permettra d'effectuer le changement dans le modèle sans avoir à changer le fonctionnement entier de la résolution. De plus, il nous permettra de résoudre le modèle en utilisant un solveur différent.
Pour une meilleure compréhension des deux scénarios, nous les avons schématisés comme suit :

Schéma du scénario 1 et 2 de la résolution du problème d'optimisation
Figure 2 : Schéma des scénarios 1 et 2

Le problème d'ordonnancement et de routage de la maintenance préventive (PMSRP) est choisi comme cas d'utilisation pour les besoins de l'expérimentation. Nous avons commencé la modélisation de PMSRP [1] avec "MiniZinc" parce qu'il est largement utilisé dans la littérature pour résoudre le problème formulé sur la base de CSP. Après avoir compilé le modèle écrit en DSL "MiniZinc", nous obtenons un fichier aplati "FlatZinc". De plus, nous pouvons écrire des contraintes complexes car lors de la compilation du modèle, le compilateur de "MiniZinc" aplatit les contraintes dans le fichier de sortie intermédiaire. L'inconvénient que nous avons rencontré jusqu'à présent avec ce DSL, c'est que les solveurs proposés par l'IDE de "MiniZinc" sont basés sur la méthode exacte. Pour résoudre notre problème de complexité NP-complet, l'expérience montre que nous pouvons résoudre un problème jusqu'à 50 activités de maintenance par jour, les solveurs intégrés dans l'IDE de "MiniZinc" (Cf. Figure 3 - IDE "MiniZinc") ne peuvent pas nous donner une solution dans un temps de calcul raisonnable (3 heures).

Environnement MiniZinc.
Figure 3 : Environnement de MiniZinc

Travaux futurs

Dans un futur proche, nous ferons une expérience complète avec "MiniZinc", en utilisant des données réelles pour pouvoir les tester avec différents solveurs. Ensuite, nous comparerons la qualité des solutions générées par les différents solveurs avec leurs performances de calcul. Enfin, nous étudierons la possibilité d'intégrer le DSL "MiniZinc" dans BL.Optim, ce qui nous aidera à améliorer l'inefficacité de la formulation de nouvelles règles métier dans différents contextes.

Par Sihem Laradi

Plus ...

Retour en haut