Concevoir la bonne façon d'exprimer les contraintes dans une architecture Java pour les problèmes d'optimisation

Nous sommes souvent amenés à résoudre des problèmes avec des contraintes dans la vie réelle, par exemple : faire des achats dans plusieurs magasins éloignés, planifier et organiser les dépenses de vacances, ou emballer des choses dans des cartons lors d'un déménagement. La résolution de ces problèmes avec contraintes n'est pas toujours facile. Plus particulièrement, lorsqu'il s'agit d'optimiser un ensemble de critères tels que le temps, le coût ou l'espace. Pour de nombreux problèmes, l'ensemble des solutions possibles est très vaste, ce qui rend impossible la comparaison des solutions possibles dans un délai raisonnable. L'automatisation de la résolution est donc nécessaire, même si elle représente aussi un véritable défi pour les machines.

Que sont les problèmes de satisfaction de contraintes ?

Ce type de problème est largement étudié dans la littérature sous le nom de " Problème de satisfaction des contraintes (CSP)" [1,3-6], qui est formellement défini par un triplet (X, D, C) où :

• X = {X_1,X_2,...,X_N} est un ensemble de variables du problème.
• D est une fonction de domaine qui associe à chaque Xi son domaine D(X_i) (valeurs possibles de X_i).
• C = {C_1,C_2,...,C_M} est un ensemble de contraintes du problème.

Une contrainte est définie par un couple (V,R) où :

• V = {V_1,V_2,...,V_R} est l'ensemble des variables liées à la contrainte.
• R est une relation qui définit l'ensemble des tuples satisfaisant la contrainte.

Pour définir un problème comme un CSP, nous devons répondre à trois questions clés :

1. Quel est l'ensemble des variables de notre problème ?
2. Quel est le domaine de chaque variable de notre problème ?
3. Et comment définir une contrainte ?

Nous avons déjà répondu à ces trois questions pour un problème d'optimisation de la planification des services de soins à domicile [2] et un problème d'optimisation de la planification des ressources matérielles et humaines pour des interventions de maintenance. Nous détaillons dans cet article le langage que nous avons proposé pour définir les contraintes.

Un langage de contraintes pour les CPS

Nous avons proposé un langage flexible et expressif pour représenter les contraintes sous forme de prédicats qui peuvent inclure des variables, des constantes et des fonctions du problème.

Une contrainte concerne une variable V, elle est définie par un ensemble de règles de restriction appliquées à la variable V. La combinaison de ces règles de restriction produit un langage très expressif pour construire des contraintes. Ce langage doit être défini avec soin, plus le langage est expressif, plus il permet de représenter de contraintes, mais l'évaluation de ces contraintes sera difficile et plus longue. Moins le langage est expressif, moins il est possible d'exprimer des contraintes, mais l'évaluation de ces contraintes sera facile et rapide.

Définition d'une contrainte

Une contrainte est définie par un couple :

• V est la variable concernée par la contrainte, chaque contrainte concerne une variable.
• R=(R_1,R_2,...,R_N) est l'ensemble des règles de restriction appliquées à la variable V.

On définit une règle de restriction R qui permet de restreindre le domaine d'une variable V. Cette restriction est réalisée par quatre opérateurs possibles : "supérieur à" pour sélectionner des valeurs supérieures à l'opérande, "inférieur à" pour sélectionner des valeurs inférieures à l'opérande, "égal à" pour redéfinir le domaine de la variable avec un ensemble d'opérandes et "différent de" pour sélectionner des valeurs différentes de l'ensemble des opérandes. Les opérandes d'un opérateur peuvent être des constantes, des variables de la CSP ou une combinaison des deux.
Une règle de restriction n'est appliquée que si toutes les conditions associées à la règle sont "vraies".

Une règle de restriction R est définie par un quadruplet (T,RC,RV,D) :

• T est le type de la règle de restriction.
• RC=( RC1, RC2,..., RCM) est l'ensemble des constantes de la règle de restriction.
• RD=(RD1, RD2,..., RDP) est l'ensemble des variables de la règle de restriction.
• D=(D1,D2,..., DZ) est l'ensemble des conditions de la règle de restriction.

Les conditions d'une règle de restriction sont utilisées lorsque l'application de la règle de restriction dépend de la valeur d'une autre variable du problème. Les conditions sont évaluées lors de l'affectation de la variable pour redéfinir son domaine.

Une condition est définie par un triplet :

•  T est le type de condition.
• OC=(OC1, OC2,..., OCM) est l'ensemble des constantes de la condition.
• OV=(OV1, OV2,..., OVM) est l'ensemble des variables de la condition.

Mise en œuvre d'une contrainte

Les contraintes sont implémentées en tant que classes Java (Figure 1):

• Classe de contrainte : c'est la classe principale. Elle contient la variable concernée par la contrainte et l'ensemble des règles de restriction associées à la variable.
• Classe RuleOfConstraint : elle permet de définir les règles permettant de restreindre le domaine de la variable. Elle est définie par son opérateur, ses opérandes et un ensemble de conditions à vérifier avant l'évaluation de la règle. Elle contient également la fonction "getDomain (...)" qui évalue la règle pour retourner le nouveau domaine de la variable.
• Classe de condition : elle définit la condition à satisfaire avant l'évaluation d'une règle de restriction. Elle est définie par un opérateur de condition et un ensemble d'opérandes (constantes et variables).

Toutes les contraintes du contexte de la planification des services de soins à domicile ou des interventions de maintenance peuvent être exprimées avec notre implémentation.

Conclusion et perspectives

En résumé, nous avons proposé un langage de contraintes pour définir les contraintes d'un CSP. Ce langage couvre une famille de sous-langages de la logique du premier ordre. Il nous permet de traiter toutes les contraintes rencontrées dans le contexte de la planification des services de soins à domicile ou de la planification des interventions de maintenance.
Le prochain objectif de notre travail est de prouver que notre langage de contraintes permet d'exprimer toutes les contraintes d'un CSP. Nous prévoyons de définir des métriques sur les contraintes pour améliorer la stratégie de sélection des variables et de travailler sur le mécanisme d'évaluation des contraintes pour l'améliorer. Nous nous intéresserons également à ce qui est fait sur les CSPs en termes de filtrage des domaines de variables, de représentation et de gestion des contraintes.

Références

[1] Sally C Brailsford, Chris N Potts, et Barbara M Smith. 1999. Constraint satisfaction problems : Algorithms and applications. Eur. J. Oper. Res. 119, 3 (1999), 557-581.
[2] Yahia Chabane, Christophe Bortolaso, et Mustapha Derras. 2019. Quand les fourmis prennent soin des humains : ACO pour l'optimisation de la planification des services de soins à domicile. In Studies in Health Technology and Informatics.
[3] Christodoulos A Floudas et Panos M Pardalos. 1990. A Collection of Test Problems for Constrained Global Optimization Problems. Springer.
[4] Kim. Marriott et P J Stuckey. 1998. Programming with constraints : an introduction. MIT Press Cambridge, Mass.
[5] Francesca Rossi, Peter van Beek, et Toby Walsh (Eds.). 2006. Handbook of Constraint Programming. Elsevier.
[6] Christine Solnon. 2010. Ant Colony Optimization and Constraint Programming. Wiley.