Programmation par contraintes

En M2 Bases de données et IA et M2 Image et IA

Par Olivier Bailleux, Maître de conférences HDR, Université de bourgogne

Partie D : résolution énumérative

Objectif

Comprendre le principe de fonctionnement d’un solveur de type MAC (Maintaining Arc Consistency) et être capable de simuler le déroulement de l’exécution d’un tel solveur sur une instance de problème dont l’arbre de recherche peut être dessiné sur une feuille A4, et d’énumérer ou comptabiliser les solutions (si applicable) de cette instance.

Prérequis

Parties A et C

Introduction

Résoudre un réseau de contraintes, c’est déterminer s’il existe au moins une assignation des variables qui satisfait toutes les contraintes. Le nombre de ces assignations étant proprement astronomique – il croît exponentiellement en fonction du nombre de variables – il n’est pas possible en pratique d’énumérer et de tester une par une toutes les assignations possibles.

La résolution dite « énumérative » ne l’est donc pas totalement mais fait aussi appel à des déductions pour accélérer la recherche d’éventuelle solutions. Dans le cas du solveur MAC que nous allons étudier, ces déductions sont des restaurations de cohérence de domaines.

L’idée de l’algorithme MAC est de décomposer le réseau de contraintes à résoudre, après restauration de la cohérence de domaines, en plusieurs réseaux plus simples dans lesquels une des variables du réseau initial a été assignée avec une des valeurs de son domaine. Par exemple, un réseau ayant une variable A de domaine {1, 2} sera décomposé en deux réseaux : un dans lequel la variable A vaut 1 et un dans lequel elle vaut 2. Chacun de ses réseaux sera filtré et si nécessaire, à nouveau décomposé sur la base d’une autre variable. La variable A est appelée variable de branchement.

D-dec-10

Soit le réseau de contraintes $(a\vee b \vee c), (\neg a \vee \neg c), (\neg b \vee c)$, où les variables $a,b,c$ ont toutes pour domaine ${0,1}$. Donnez les réseaux obtenus pour $a=0$ et $a=1$.

D2 : Algorithme MAC

Cette version de l’algorithme produit toutes les solutions. On peut la modifier pour qu’elle s’arrête dès qu’une solution est trouvée.

Simulons l’exécution de cet algorithme sur le réseau suivant :

La première chose à faire est de restaurer la cohérence de domaines. Cela peut permettre de simplifier le problème avant de faire le premier branchement. Voici le résultat du filtrage.

Si ce résultat vous paraît étonnant, c’est que vous ne maîtrisez pas le badge C, qui est un prérequis (où que le rédacteur du présent document s’est trompé).

Le filtrage simplifie le réseau (ce n’est pas toujours le cas), mais ne produit pas immédiatement de solution et ne fait pas apparaître d’incohérence (domaine vide).

Il nous faut donc choisir une variable de branchement. Nous allons utiliser la variable A. Nous obtenons l’arbre de recherche suivant, qui permet d’énumérer les deux solutions du réseau. Selon les besoins, on peut arrêter la recherche à la première solution ou n’énumérer qu’une partie des solutions. Si toute les branches de l’arbre de recherche aboutissent à une incohérence (domaine vide après filtrage), on conclut à l’incohérence du réseau.

En pratique, pour présenter une simulation de résolution, on ne redessinera pas tout le réseau de contraintes à chaque nœud, mais seulement les domaines et les variables de branchement.

D-dec-20

Est-il plus avantageux, moins avantageux ou aussi avantageux d’utiliser la variable $B$ comme variable de branchement à la racine de l’arbre de recherche ?

D3 : variantes

Filtrage affaibli

Dans l’algorithme MAC, un filtrage complet par restauration de cohérence de domaine est réalisé à chaque nœud (y compris racine) de l’arbre de recherche. Ce filtrage est généralement rentable dans la mesure où le temps qu’il consomme est largement compensé par la réduction du nombre de branchements, donc de la taille de l’arbre de recherche. Mais il peut y avoir des exceptions pour certaines contraintes dont la restauration de cohérence de domaines est couteuse, pour lesquelles on peut utiliser un filtrage plus « faible ».

Par exemple, restaurer la cohérence de domaine sur une contrainte de type $a_{1} x_{1} + \ldots + a_{n} x_{n} = b$, où $a_{1}, \ldots, a_{n}$ et $b$ sont des entiers relatifs, est très couteux. On ne connait aucun algorithme capable de le faire en temps polynomial. (Ce qui est contre-intuitif !)

On peut utiliser à la place un filtrage très rapide bien que moins puissant, qui consiste à restaurer la cohérence de domaine sur les deux contraintes $a_{1} x_{1} + \ldots + a_{n} x_{n} \leq b$ et $a_{1}\ x_{1} + \ldots + a_{n} x_{n} \geq b$. Même si cela vous paraît très étrange en première lecture, restaurer la cohérence de domaine sur les deux inégalités ne permet pas de la restaurer sur l’égalité.

Pas convaincu ?

D-dec-30

Restaurez la cohérence de domaine sur le réseau de contraintes suivant, avec domaine {0,1} pour toutes les variables :

• $q_{1}: x_{1} + 2x_{2} + 3x_{3} + 4x_{4} \leq 6$

• $q_{2}: x_{1} + 2x_{2} + 3x_{3} + 4x_{4} \geq 6$

D-dec-31

A présent, toujours avec les mêmes domaines initiaux {0,1}, restaurez la cohérence de domaine sur la contrainte suivante :

• $q : x_{1} + 2x_{2} + 3x_{3} + 4x_{4} = 6$

Ce n’est pas immédiat à réaliser. Il faut se poser des questions du genre « est-il possible d’obtenir une somme égale à 6 si $x_{1}$ vaut 1 ? »

La restauration de la cohérence de domaines sur $q$ a permis de faire un filtrage qui n’a pas été réalisé par la restauration de la cohérence de domaines sur $q_{1}$ et $q_{2}$. Mais faute de disposer d’un algorithme efficace pour les contraintes telles que $q$, c’est-à-dire les égalités pseudo-Booléennes, on peut appliquer à ces contraintes des filtrages moins puissants qui restaurent la cohérence de domaines sur leur décomposition en deux inégalités pseudo-Booléennes.

Dans certains cas, contrairement à ce qui s’est produit dans notre exemple, ce filtrage affaibli réduit certains domaines et c’est mieux que rien.

Filtrage partiel

La restauration de cohérence de domaines s’applique itérativement à toutes les contraintes d’un réseau jusqu’à ce que toutes les valeurs de chaque domaine aient au moins un support pour toutes les contraintes. On peut réduire le coût du filtrage – et son efficacité – en ne filtrant que les contraintes directement reliées à la variable de branchement. L’algorithme obtenu est appelé forward checking (FC).

MAC est en général plus rapide que FC, mais on ne peut en faire un dogme. Dans certains cas particuliers où le filtrage complet serait couteux et peu rentable, on peut envisager d’utiliser FC, en prolongeant toutefois le filtrage lorsque certains domaines deviennent des singletons.

Dans le cadre de cet enseignement, on travaillera uniquement avec MAC.

Au delà de la cohérence de domaines

La restauration de la cohérence de domaines déduit tout ce qu’il est possible de déduire à partir d’une seule contrainte et lorsque la conclusion de la déduction est une restriction des domaines. Mais on peut imaginer d’autres formes de déductions faisant intervenir plusieurs contraintes. Lorsque le résultat d’une telle déduction est une nouvelle contrainte, on parlera d’apprentissage, mais si le résultat est une restriction de domaines on peut encore parler de filtrage.

L’exemple typique est la notion de k-cohérence, souvent appelée k-consistance dans la littérature par francisation du terme anglais consistency qui se dit en français cohérence. Un réseau de contraintes et k-cohérent si toute assignation partielle de k-1 variables peut être étendue à une assignation partielle de k variables sans falsifier de contrainte.

Cette notion ne sera pas développée ici, mais rien n’empêche de remplacer dans un solveur de type MAC la restauration de la cohérence de domaines par la restauration de la k-cohérence. Le risque est que le coût d’un tel filtrage soit plus élevé que son bénéfice, mais rien ne permet d’affirmer qu’il ne soit pas rentable pour certains types de contraintes ou de réseaux.

Branchements binaires

Dans l’algorithme MAC décrit au début de ce document, chaque nœud de l’arbre de recherche est associé à une certaine variable de branchement, appelons-là $V$, et chaque branche partant de ce nœud correspond à une valeur du domaine de $V$. On peut donc avoir des nœuds à deux, trois, quatre branches et plus. On peut interpréter ces branchements comme des hypothèses. En branchant sur $V = x$, où $x$ est dans le domaine de $V$, on fait l’hypothèse qu’il existe au moins une solution pour laquelle $V = x$. Si cette hypothèse est vraie, on trouvera de telles solutions dans le sous-arbre induit par le branchement. Si elle est fausse, on aura acquis une connaissance, à savoir qu’avec les domaines considérés avant le branchement, il n’existe aucun moyen de satisfaire le réseau si $V = x$. Cette connaissance est enregistrée implicitement par le solveur grâce au mécanisme qu’il utilise pour éviter de faire à nouveau le branchement $V = x$ à partir du même nœud de son arbre de recherche. On parle parfois de phase de la variable de branchement.

Il existe une variante de MAC dans laquelle on réalise exactement deux branchements à chaque nœud. Dans cette variante, pour une variable de branchement $V$, on va avoir un branchement correspondant à l’hypothèse $V = x$ et un autre correspondant à l’hypothèse $V \neq x$.

Tout arbre de MAC classique peut être aisément simulé par un MAC à branchements binaires. Par exemple dans le cas d’une variable de branchement $V$ de domaine ${ 1,2,3}$, le deuxième branchement correspondant à $V \neq 1$ pourra être prolongé par un branchement basé sur la même variable $V$ avec les hypothèses $V = 2$ et $V \neq 2$, mais comme à ce stade il n’y aura plus que 2 et 3 dans le domaine de $V$, cela reviendra au même que brancher sur $V = 2$ et $V = 3$.

La réciproque n’est pas vraie. MAC à branchements binaires peut produire des arbres de recherche impossibles à obtenir avec MAC classique.

MAC à branchements binaires peut être plus efficace que MAC classique sur certains problèmes, à condition de bien choisir les variables et valeurs de branchements. Or ce choix est loin d’être évident, comme nous le verrons plus loin.

D-dec-32

Soit le réseau de contraintes suivant :

• Variables : $A, B, C$ ayant toutes pour domaine ${1,2,3}$.

• Contraintes : $\text{allDiff}(A,B,C)$, $A+B=4$.

Donnez l’arbre de recherche MAC à branchement binaire en utilisant $A$ comme première variable de branchement.

Apprentissage (approfondissement hors programme)

Dans MAC classique et MAC à branchements binaires, il y a une forme d’apprentissage dans le sens où le solveur accumule des connaissances sur des assignations partielles qui ne peuvent être étendues à des solutions. Prenons comme exemple l’arbre de recherche suivant (peu importe les contraintes).

Cet arbre est parfaitement plausible. Rien n’oblige à choisir les variables de branchement dans le même ordre sur chaque branche. D’autre part, en raison des filtrages réalisés à chaque nœud, une même variable de branchement peut avoir un domaine différent selon le nœud où elle est utilisée. Les croix représentent des échecs, ou incohérences, c’est-à-dire des situations où après branchement et filtrage, un domaine devient vide.

Intéressons-nous au moment où la recherche vient de produire le quatrième échec. A ce moment précis, le solveur à accumulé les connaissances suivantes :

• Il n’y a pas de solution avec $A = 1$.

• Il n’y a pas de solution avec $A = 2$ et $C = 1$.

C’est ce que l’auteur de ce cours appelle de l’apprentissage implicite. C’est le mécanisme de retour arrière qui permet au solveur de conserver ces connaissances. Par exemple, après le stade matérialisé sur la figure ci-dessus, le solveur n’essaiera plus de trouver des solutions avec $A = 1$, ni avec $A = 2$ et $C = 1$.

Mais certains mécanismes d’apprentissage explicite peuvent être ajouté au solveur. Il peut s’agir de systèmes déductifs activés au moment des échecs. Par exemple, imaginons que le deuxième échec ne dépende pas de la valeur de la variable $A$. On dira que ${B = 5,\ C = 1}$ est un nogood. Trouver ce genre de nogood requiert des algorithmes spécifiques qui sortent du périmètre de ce cours.

Si notre algorithme MAC était équipé d’un mécanisme permettant de détecter le nogood ${B = 5,\ C = 1}$, alors on pourrait ajouter cette information dans une base de connaissances ou l’ajouter au réseau comme une nouvelle contrainte. Ainsi, si par exemple l’assignation $B = 5$ se reproduit plus tard, la valeur $1$ sera retirée du domaine de $C$, ce qui évitera des branchements qui auraient été nécessaires sans cet apprentissage.

En pratique, les solveurs avec apprentissage sont très complexes et font généralement des redémarrages et des retours arrière non chronologiques, c’est-à-dire qu’après certains échecs et apprentissages associés, ils remontent plus haut que la dernière variable de branchement même si toutes les valeurs du domaine de cette variable n’ont pas été essayées.

Les nogoods ou autres connaissances qu’ils apprennent occupent un espace mémoire important, ce qui impose de retirer régulièrement certaines connaissances apprises. Malgré cette grande complexité, ces solveurs peuvent être beaucoup plus efficaces que les solveurs sans apprentissage (ou à apprentissage implicite). Par exemple pour problème SAT, dans lequel les contraintes sont des clauses en logique propositionnelle, les solveurs de type CDCL (pour Conflict Driven Clause Learning) qui apprennent (comme leur nom l’indique) de nouvelles clauses, pulvérisent les performances des solveurs énumératifs de type MAC (qui dans le contexte de SAT sont appelés DPLL d’après les initiales des noms des inventeurs).

D4 : Heuristiques de branchement

Le choix des variables de branchement (et des valeurs dans le cas de la version à branchement binaire) est critique pour l’efficacité des solveurs de type MAC. Sur des réseaux de quelques dizaines de variables, on peut facilement observer des rapports de temps d’exécution de l’ordre du milliard, ou beaucoup plus, selon la manière dont les variables de branchement sont choisies.

Pour comprendre l’importance de choisir les « bonnes » variable de branchement, considérons cet exemple.

La cohérence de domaine est vérifiée pour toutes les contraintes. (Rappelez-vous que cette forme de cohérence ne considère qu’une seule contrainte à la fois !).

Si MAC commence par brancher avec une des variables A, B ou C, il déduira rapidement que le réseau est incohérent. Mais s’il commence par la variable D, il revérifiera trois fois l’incohérence du sous-réseau A, B, C.

Trouver la meilleure variable de branchement est (dans le cas général) plus difficile que résoudre le réseau, mais il existe des heuristiques de choix de la variable de branchement qui sont plus ou moins efficaces selon la nature des contraintes et la structure du réseau.

On appelle heuristique un critère de choix facile à calculer (qui prend un temps faible au regard des autres traitement réalisé par le solveur) mais qui ne donne aucune garantie d’optimalité.

Ces heuristiques peuvent prendre en compte, par exemple :

• la taille du domaine de chaque variable,

• le nombre de contraintes dans lesquelles chaque variable intervient,

• le nombre d’assignations partielles autorisées par chaque contraintes,

• des poids attribués à chaque variable, qui évoluent au cours de la recherche en fonction de l’efficacité des filtrages réalisés sur leurs domaines (on parle alors d’heuristiques dynamiques)…

C’est un très vaste sujet que nous n’approfondirons pas ici. Même lorsque le réseau de contraintes est cohérent, c’est le choix des variables de branchement qui est particulièrement critique pour trouver une solution. Bien évidemment, si on pouvait « deviner » les assignations des variables d’une solution, on la trouverait immédiatement quelles que soient les variables de branchement. Mais en pratique il s’avère souvent que « deviner » les solutions à l’aide d’une heuristique ne fonctionne pas, alors que les heuristiques efficaces pour prouver l’incohérence du réseau de contraintes sont celles qui sont également les plus efficaces pour trouver des solutions lorsque le réseau de contraintes est cohérent.

Exercices d’assimilation

D-ass-01

Complétez cet arbre de recherche de l’algorithme MAC sur le problème des 5 reines. Chaque pastille ronde rose représente l’assignation d’une variable de branchement. Les croix grises représentent les valeurs des domaines des variables qui ont été filtrées (ou éliminées du fait de l’assignation de la variable). Les pastilles carrées roses représentent les valeurs assignées par filtrage (quand il ne reste qu’une valeur dans le domaine concerné). On considère qu’il y a 10 contraintes reliant respectivement A et B, A et C, A et D, A et E, B et C, B et D, B et E, C et D, C et E, D et E. Chacune de ces contraintes exprime que les reines situées sur les colonnes associées aux variables concernées ne sont ni sur une même ligne, ni sur une même diagonale.

D-ass-02

Soit le problème suivant :

Variables :

Contraintes :

Pour chaque ligne et chaque colonne, une contrainte exprime que la somme des variables concernées vaut 2. $A + B + C = 2$, $D + E + F = 2$, $G + H + I = 2$, $A + D + G = 2$,$B + E + H = 2$, $C + F + I = 2$.

Réalisez une simulation de l’exécution d’un solveur MAC sur cette instance de problème. Dessinez l’arbre de recherche complet (recherchant toutes les solutions), en précisant à chaque nœud les domaines des différentes variables. Pour faciliter la lecture, merci de représenter ces domaines sous la forme d’une grille de 3 par 3 avec la convention suivante : une case blanche représente le domaine {0,1} , une case contenant la valeur 0 représente le domaine {0} , et une case contenant la valeur 1 représente le domaine {1}.

D-ass-03

Soit le réseau de contraintes suivant :

• Variables : A avec domaine {0,5}, B avec domaine {0,6}, C avec domaine {0,9}, D avec domaine {0,2}.

• Contraintes : A + B + C + D >= 15 et A + B + C + D <= 15.

Détaillez la résolution de ce problème par l’algorithme MAC (Maintaining Arc Consistency). Choisissez les variables de branchement de manière à minimiser la taille de l’arbre de recherche.

D-ass-04

Soit le réseau constitué des 6 contraintes logiques suivantes, appelées clauses.

$$(a \vee b), (\neg a \vee b), (a \vee \neg b), (\neg a \vee \neg b \vee c), (\neg c \vee d), (\neg c \vee \neg d)$$

Les variables ont toutes pour domaine {0,1}.

Détaillez la résolution de ce problème par l’algorithme MAC. A chaque nœud ou feuille, redonnez les domaines en barrant les valeurs éliminées par filtrage ou par assignation de la variable de branchement. A chaque feuille, précisez s’il y a échec ou solution. Essayez de choisir les variables de branchement de manière à minimiser la taille de l’arbre de recherche.

Programmation par contraintes

En M2 Bases de données et IA et M2 Image et IA

Par Olivier Bailleux, Maître de conférences HDR, Université de bourgogne

Implémentation avec CHOCO v4

Objectif

Être capable de concevoir une application Java permettant de résoudre un problème de satisfaction de contraintes en utilisant la bibliothèque CHOCO version 4.

Prérequis

Partie B et bases de programmation en JAVA.

Introduction

Entendons-nous bien. La programmation par contraintes est une programmation déclarative : on spécifie un problème à l’aide de contraintes, et un solveur résout ce problème. L’intérêt est précisément de ne pas avoir à programmer un solveur. Java n’est pas un langage déclaratif mais impératif, qui exige de détailler toutes les étapes et opérations nécessaires à l’exécution d’un programme.

Alors pourquoi et comment utiliser un langage impératif pour faire de la programmation déclarative ?

Il faut comprendre que les applications réalisées avec la bibliothèque CHOCO s’exécutent en deux temps. Dans un premier temps, un programme Java produits des objets de types variables et contraintes, qui sont placés dans un objet appelé modèle, qui représente un réseau de contraintes.

Une application utilisant CHOCO exécute un algorithme qui « fabrique » une spécification déclarative d’un problème de satisfaction de contraintes. Dans un deuxième temps, un objet solveur prend en charge le modèle préalablement construit pour résoudre le réseau de contraintes. Donc le code Java ne sert pas à résoudre le problème, mais à construire des réseaux de contraintes représentant des instances du problème à résoudre. La résolution en elle-même est assurée par le solveur fourni par CHOCO.

Avant d’aller plus loin, vous devez récupérer la bibliothèque CHOCO qui est disponible sous la forme d’une archive au format jar en suivant les instructions du site choco-solver.org. On vous envoie vers un dépôt github où, en cherchant bien, vous pourrez trouver un lien vers la "latest release". Au moment où j’écris ces lignes, il s’agit de la version 4.10.6. Vous arrivez enfin à une page proposant plusieurs archives. Celle qui nous intéresse est nommée choco-solver-4.10.6-jar-with-dependencies.jar au moment où j’écris ce ligne. Il se peut qu’il s’agisse d’une version ultérieur lorsque vous vous rendrez sur le site, mais l’important est que la bonne archive a l’extension jar et comporte les termes choco-solver et with-dependencies dans son nom.

Vous devez ensuite faire en sorte d’utiliser cette bibliothèque dans le code Java que vous allez écrire et compiler. Les IDE proposent tous un moyen spécifique de faire cela. Il faut parfois tâtonner un peu.

Exemple introductif

Avant de coder une application CHOCO, il faut modéliser le problème à résoudre sous la forme d’un réseau de contraintes comme nous avons appris à le faire dans la préparation du badge B.

Nous parlons ici du problème suivant : peut-on placer n reines sur un échiquier n par n de manière à qu’il y ait exactement une reine sur chaque ligne et chaque colonne et au plus une reine sur chaque diagonale ?

Pour modéliser ce problème, nous utilisons $n$ variables $v_{0},\ldots,\ v_{n – 1}$ à domaines ${ 1..n}$. Chaque variable est associée à une colonne de l’échiquier. Une assignation $v_{i} = j$ signifie que la reine située dans la colonne $i$ se trouve en ligne $j$.

La figure ci-dessous représente une solution pour $n = 5$ et l’assignation des variables $v_{0}$ à $v_{4}$ qui représente cette solution.

Pour chaque couple $(i,j),\ i \in 0..(n – 2),\ j \in (i + 1)..(n – 1)$, on pose les trois contraintes suivantes :

1. $v_{i} \neq v_{j}$, qui interdit que les reines des colonnes $i$ et $j$ soient une même ligne.

2. $v_{i} \neq v_{j} – (j – i)$, qui interdit que les reines des colonnes $i$ et $j$ soient sur une même diagonale descendante.

3. $v_{i} \neq v_{j} + (j – i)$, qui interdit que les reines des colonnes $i$ et $j$ soient sur une même diagonale montante.

Par exemple, on aura trois contraintes reliant les variables $v_{0}$ et $v_{2}$, à savoir $v_{0} \neq v_{2}$, $v_{0} \neq v_{2} – 2$ et $v_{0} \neq v_{2} + 2$. Si par exemple $v_{0} = 3$, ces trois contraintes interdiront les valeurs 2, 4 et 6 pour $v_{2}$.

Au total, pour $n$ reines, on aura $3n(n – 1)/2$ contraintes.

Il nous faut maintenant traduire ce modèle en un ensemble d’objets créés avec la bibliothèque CHOCO. Voici les différentes étapes.

Création du modèle

Ces deux lignes permettent de créer un modèle (instance de la classe Model) à laquelle seront ensuite ajoutées les contraintes et les variables. La chaîne passée en paramètre est purement « cosmétique ».

    int n = 8;
    Model model = new Model(n + "-queens problem");

Création des variables

Ces lignes permettent de créer les variables du réseau de contraintes. Attention. Nous parlons bien ici des variables du réseau de contraintes, dont les domaines contiennent des entiers. Ces variables ne sont pas des variables de type int de Java. Ce sont des instances de la classe IntVar de CHOCO qui représentent les variables du réseau de contraintes sur lequel le solveur CHOCO va raisonner.

    IntVar[] vars = new IntVar[n];
    for(int q = 0; q < n; q++)
    {
        vars[q] = model.intVar("Q_"+q, 1, n);
    }

La première ligne crée un tableau qui regroupera toutes les variables du problème. Attention, cette liste produit juste un tableau dont les cellules contiennent la pseudo-référence null.

En Java, les cellules d’un tableau, tout comme les variables ayant un type non scalaire T ne contiennent jamais une instance de type T, mais contiennent soit la valeur null, soit la référence d’un objet de type T.

En résumé, une variable ou une cellule de tableau ne peut pas contenir un objet, mais seulement sa référence. Donc dans notre cas, la création du tableau ne crée pas les variables de notre réseau mais juste les cellules destinées à contenir les références de ces variables.

C’est la boucle for qui va créer les variables de notre réseau de contraintes, qui est appelé modèle dans la documentation CHOCO, et placer les références de ces variables, représentées par des objets de type IntVar, dans le tableau vars.

La création de chaque variable est assurée par la méthode intvar de la classe Model de CHOCO.

L’appel model.intVar(\"Q\_\"+q, 1, n) retourne la référence un objet de type IntVar qui représente une variable (au sens de la programmation par contrainte) nommée Q_q (où q désigne la colonne associée à la variable) et de domaine 1..n (où n est le nombre de reines). Le nom de la variable est un attribut purement cosmétique qui pourra servir pour des affichages et lors de la mise au point du programme.

Création des contraintes

Les contraintes de notre modèle sont des objets de type Constraint. Ces objets sont produits par la méthode arithm de la classe Model. Différentes variantes surchargées de cette méthode permettent de construire aisément des contraintes arithmétiques à partir de variables, d’opérateurs et de constantes comme le montrent les lignes de code suivantes qui créent les contraintes pour le problème de n reines et les intègrent dans le modèle.

    for(int i  = 0; i < n-1; i++)
    {
        for(int j = i + 1; j < n; j++)
        {
            model.arithm(vars[i], "!=",vars[j]).post();
            model.arithm(vars[i], "!=", vars[j], "-", j - i).post();
            model.arithm(vars[i], "!=", vars[j], "+", j - i).post();
        }
    }

Examinons par exemple la ligne model.arithm(vars\[i\], \"!=\", vars\[j\], \"-\", j - i).post(). Cette ligne appelle la méthode arithm qui, avec les paramètres qui lui sont transmis, crée un objet de type Constraint représentant la contrainte $v_{i} \neq v_{j} – (j – i)$. La méthode post de la classe Constraint est ensuite appelée pour intégrer cette contrainte dans le modèle dans lequel elle a été créée. Il faut bien comprendre que du point de vue de CHOCO, les valeurs des variables Java i et j sont des constantes qui vont être figées dans la contrainte au moment de sa création.

En pratique, toutes les contraintes créées dans un modèle doivent y être intégrées par la méthode post sauf les contraintes dites réifiées.

La réification d’une contrainte $q$ sur un ensemble $V$ de variables est une contrainte $q^{r}$ sur $V \cup { r}$, où $r$ est une variable additionnelle appelée variable de réification à domaine Booléen {0,1}, telle que pour toute assignation $A$ sur $V$, $A \cup { r = 1}$ satisfait $q^{r}$ si et seulement si $A$ satisfait $q$ et $A \cup { r = 0}$ satisfait $q^{r}$ si et seulement si $A$ falsifie $q$. En résumé, la réification $q^{r}$ d’une contrainte $q$ peut toujours être satisfaite mais avec une valeur de sa variable de réification qui indique si $q$ est satisfaite par les valeurs des autres variables.

Si cela vous parait confus, pour l’instant retenez juste que pour ajouter des contraintes ordinaires, telle que celles que nous avons vu dans la préparation des parties A et B, il faut toujours intégrer les contraintes avec la méthode post et que si vous oubliez de le faire, le solveur ne prendra pas en compte les contraintes concernées.

Dans notre exemple, les boucles for imbriquées ne servent donc en aucun cas à résoudre le problème des n reines. Elles servent à fabriquer les contraintes qui spécifient ce problème et à intégrer ces contraintes dans le modèle qui servira ensuite au solveur pour résoudre le problème.

Résolution

Pour résoudre notre problème, il suffit de créer un objet de type Solveur et d’exécuter une méthode de cet objet permettant de lancer la résolution du réseau de contraintes spécifiée par le modèle précédemment construit. C’est ce que font les lignes de code ci-dessous.

    Solution solution = model.getSolver().findSolution();
    if(solution != null)
    {
        System.out.println(solution.toString());
    }

La méthode getSolver crée un objet de type Solver dédié au modèle représenté par l’objet model. La méthode findSolution appelée avec cet objet recherche une solution de ce modèle. Si le réseau de contraintes représenté par le modèle est incohérent, findSolution retourne null, sinon elle retourne un objet de type Solution qui contient les détails de la solution trouvée. La méthode toString de l’objet solution permet d’afficher les valeurs assignées aux variables par cette solution.

Il existe d’autres méthodes applicables aux objets de type Solver pour rechercher toutes les solutions du problème.

Voici le code complet de cet exemple introductif avec les imports des packages de CHOCO requis pour son fonctionnement.

public static void main(String[] args)
{
    int n = 8;
    Model model = new Model(n + "-queens problem");
    IntVar[] vars = new IntVar[n];
    for(int q = 0; q < n; q++)
    {
        vars[q] = model.intVar("Q_"+q, 1, n);
    }
    for(int i  = 0; i < n-1; i++)
    {
        for(int j = i + 1; j < n; j++)
        {
            model.arithm(vars[i], "!=",vars[j]).post();
            model.arithm(vars[i], "!=", vars[j], "-", j - i).post();
            model.arithm(vars[i], "!=", vars[j], "+", j - i).post();
        }
    }
    Solution solution = model.getSolver().findSolution();
    if(solution != null)
    {
        System.out.println(solution.toString());
    }
}

L’auteur a compilé ce code dans l’IDE IntelliJIDEA et l’exécution a produit l’affichage suivant :

Solution: Q_0=7, Q_1=4, Q_2=2, Q_3=5, Q_4=8, Q_5=1, Q_6=3, Q_7=6

Voici une représentation graphique de la solution trouvée par le solveur.

Exercices d’assimilation

A-ass-00

Le problème des reines en booléens. On modélise le problème des $N$ reines en utilisant uniquement des variables Booléennes. Le réseau de contraintes comporte $N^{2}$ variables, chacune associée à une case de l’échiquier. Voici par exemple les variables pour $N = 5$.

Une contrainte est associée à chaque ligne, chaque colonne et chaque diagonale de l’échiquier. Les contraintes relient toutes les variables d’une même ligne ou d’une même colonne expriment qu’une seule des variables concernées vaut 1. Les contraintes qui relient toutes les variables d’une même diagonale expriment qu’au plus une des variables concernées vaut 1.

Voici deux exemples de contraintes pour $N = 5$.

Réalisez une application CHOCO qui résout ce problème.

    int N = 8;

    //Création du modèle
    Model model = new Model(N + "-queens problem");

    // Création des variables
    IntVar[][] x = new IntVar[N][N];
    for(int i=0; i<N; i++)
    {
        for(int j=0; j<N; j++)
        {
            x[i][j] = model.intVar("X_"+i+"_"+j, 0, 1);
        }
    }

    for(int i=0; i<N; i++)
    {
        model.sum(x[i], "=", 1).post();
    }

    for(int j=0; j<N; j++)
    {
        IntVar[] col = new IntVar[N];
        for(int i=0; i<N; i++)
        {
            col[i] = x[i][j];
        }
        model.sum(col, "=", 1).post();
    }

    //Diagonales montantes
    ArrayList<IntVar>[] dUp = new ArrayList[2*N-1];

    for(int k=0; k<2*N-1; k++)
    {
        dUp[k] = new ArrayList<>();
    }

    for(int i=0; i<N; i++)
    {
        for(int j=0; j<N; j++)
        {
            dUp[i+j].add(x[i][j]);
        }
    }

    for(int k=0; k<2*N-1; k++)
    {
        IntVar[] tmp = dUp[k].toArray(new IntVar[0]);
        model.sum(tmp, "<=", 1).post();
    }

    //Diagonales descendantes
    ArrayList<IntVar>[] dDown = new ArrayList[2*N-1];

    for(int k=0; k<2*N-1; k++)
    {
        dDown[k] = new ArrayList<>();
    }

    for(int i=0; i<N; i++)
    {
        for(int j=0; j<N; j++)
        {
            dDown[i-j+N-1].add(x[i][j]);
        }
    }

    for(int k=0; k<2*N-1; k++)
    {
        IntVar[] tmp = dDown[k].toArray(new IntVar[0]);
        model.sum(tmp, "<=", 1).post();
    }

    //Résolution
    Solution solution = model.getSolver().findSolution();
    if(solution != null)
    {
        System.out.println(solution.toString());
    }

A-ass-01

Le problème du sac à dos. Les données du problème sont les suivantes :

• Deux entiers $W$ et $V$ représentant respectivement le poids maximum et la valeur minimum des objets à mettre dans un sac à dos.

• Une liste $w_{0},\ldots w_{n – 1}$ des poids des objets susceptibles d’être mis dans le sac.

• Une liste $v_{0},\ldots v_{n – 1}$ des valeurs des objets susceptibles d’être mis dans le sac.

Les variables du problème, $x_{0},\ldots,x_{n}$ ont toutes pour domaine {0,1}.

Les contraintes sont : $\sum_{i = 0}^{n – 1}{w_{i}\ x_{i}} \leq W$ et $\sum_{i = 0}^{n – 1}{\text{wv}{i}\ x{i}} \geq V$.

Réalisez une application CHOCO qui résout ce problème et testez-là avec l’instance suivante :

• Poids des objets (en kg) : 2, 5, 7, 8, 15, 21, 23

• Prix correspondants (en Euros) : 3, 11, 8, 10, 10, 8, 9

• Valeur minimum des objets emportés : 40 Euros

• Poids maximum des objets emportés : 50 Kgs

    int W = 50;
    int V = 40;
    int[] w = new int[]{2,5,7,8,15,21,23};
    int[] v = new int[]{3,11,8,10,10,8,9};

    //Création du modèle
    Model model = new Model("Backpack");

    // Création des variables
    int N = w.length;
    IntVar[] x = new IntVar[w.length];
    for(int i=0; i<N; i++)
    {
        x[i] = model.intVar("X_"+i, 0, 1);
    }

    // Création des contraintes
    model.scalar(x, w, "<=", W).post();
    model.scalar(x, v, ">=", V).post();

    //Résolution
    Solution solution = model.getSolver().findSolution();
    if(solution != null)
    {
        System.out.println(solution.toString());
    }