Session 1 :
Contraintes et Problèmes de satisfaction de contraintes


Sommaire de la session 1 :

1 - Qu'est-ce qu'une contrainte ?
2 - Qu'est ce qu'un CSP ?
3 - Un premier exemple : le problème des reines
4 - Un deuxième exemple : le problème des mariages stables

1 - Qu'est-ce qu'une contrainte ?

Une contrainte est une relation logique (une propriété qui doit être vérifiée) entre différentes inconnues, appelées variables, chacune prenant ses valeurs dans un ensemble donné, appelé domaine. Ainsi, une contrainte restreint les valeurs que peuvent prendre simultanément les variables. Par exemple, la contrainte "x + 3*y = 12" restreint les valeurs que l'on peut affecter simultanément aux variables x et y.

1.1 - Quelques caractéristiques des contraintes

Une contrainte est relationnelle : elle n'est pas "dirigée" comme une fonction qui définit la valeur d'une variable en fonction des valeurs des autres variables.

Ainsi, la contrainte "x - 2*y = z" permet de déterminer z dès lors que x et y sont connues, mais aussi x dès lors que y et z sont connues et y dès lors que x et z sont connues.

Notons également qu'une contrainte est déclarative : elle spécifie quelle relation on doit retrouver entre les variables, sans donner de procédure opérationnelle pour effectivement assurer/vérifier cette relation.

Ainsi, lorsqu'on pose la contrainte "x - 2*y = z", on ne s'occupe pas de donner un algorithme permettant de résoudre cette équation.

Notons enfin que l'ordre dans lequel sont posées les contraintes n'est pas significatif : la seule chose importante à la fin est que toutes les contraintes soient satisfaites (...cependant, dans certains langages de programmation par contraintes l'ordre dans lequel les contraintes sont ajoutées peut avoir une influence sur l'efficacité de la résolution... on y reviendra plus tard).

1.2 - Définition d'une contrainte

Une contrainte est une relation entre différentes variables. Cette relation peut être définie en extension ou en intension :

1.3 - Arité d'une contrainte

L'arité d'une contrainte est le nombre de variables sur lesquelles elle porte. On dira que la contrainte est

1.4 - Différents types de contraintes

On distingue différents types de contraintes en fonction des domaines de valeurs des variables :

2 - Qu'est ce qu'un CSP ?

2.1 - Définition d'un CSP

Un CSP (Problème de Satisfaction de Contraintes) est un problème modélisé sous la forme d'un ensemble de contraintes posées sur des variables, chacune de ces variables prenant ses valeurs dans un domaine. De façon plus formelle, on définira un CSP par un triplet (X,D,C) tel que Par exemple, on peut définir le CSP (X,D,C) suivant :
Ce CSP comporte 4 variables a, b, c et d, chacune pouvant prendre 2 valeurs (0 ou 1). Ces variables doivent respecter les contraintes suivantes : a doit être différente de b ; c doit être différente de d et la somme de a et c doit être inférieure à b.

2.2 - Solution d'un CSP

Etant donné un CSP (X,D,C), sa résolution consiste à affecter des valeurs aux variables, de telle sorte que toutes les contraintes soient satisfaites. On introduit pour cela les notations et définitions suivantes :

2.3 - Notion de CSP surcontraint ou souscontraint

Lorsqu'un CSP n'a pas de solution, on dit qu'il est surcontraint : il y trop de contraintes et on ne peut pas toutes les satisfaire. Dans ce cas, on peut souhaiter trouver l'affectation totale qui viole le moins de contraintes possibles.

Un tel CSP est appelé max-CSP (max car on cherche à maximiser le nombre de contraintes satisfaites).
Une autre possibilité est d'affecter un poids à chaque contrainte (une valeur proportionnelle à l'importance de cette contrainte, et de chercher l'affectation totale qui minimise la somme des poids des contraintes violées.
Un tel CSP est appelé CSP valué (VCSP).
Il existe encore d'autre types de CSPs, appelés CSPs basés sur les semi-anneaux (semiring based CSPs), permettant de définir plus finement des préférences entre les contraintes.

Inversement, lorsqu'un CSP admet beaucoup de solutions différentes, on dit qu'il est sous-contraint. Si les différentes solutions ne sont pas toutes équivalentes, dans le sens où certaines sont mieux que d'autres, on peut exprimer des préférences entre les différentes solutions. Pour cela, on ajoute une fonction qui associe une valeur numérique à chaque solution, valeur dépendante de la qualité de cette solution. L'objectif est alors de trouver la solution du CSP qui maximise cette fonction.

Un tel CSP est appelé CSOP (Constraint Satisfaction Optimisation Problem).

3 - Un premier exemple : le problème des reines

3.1 - Description du problème

Il s'agit de placer 4 reines sur un échiquier comportant 4 lignes et 4 colonnes, de manière à ce qu'aucune reine ne soit en prise. On rappelle que 2 reines sont en prise si elles se trouvent sur une même diagonale, une même ligne ou une même colonne de l'échiquier.

3.2 - Modélisation sous la forme d'un CSP

Pour modéliser un problème sous la forme d'un CSP, il s'agit tout d'abord d'identifier l'ensemble des variables X (les inconnues du problème), ainsi que la fonction D qui associe à chaque variable de X son domaine (les valeurs que la variable peut prendre). Il faut ensuite identifier les contraintes C entre les variables. Notons qu'à ce niveau, on ne se soucie pas de savoir comment résoudre le problème : on cherche simplement à le spécifier formellement. Cette phase de spécification est indispensable à tout processus de résolution de problème ; les CSPs fournissent un cadre structurant à cette formalisation.

Un même problème peut généralement être modélisé par différents CSPs. Pour ce problème, on peut par exemple en proposer 3. On verra plus tard que la modélisation choisie peut avoir une influence sur l'efficacité de la résolution.

Les reines / Première modélisation

Les "inconnues" du problème sont les positions des reines sur l'échiquier. En numérotant les lignes et les colonnes de l'échiquier de la façon suivante

1 2 3 4
1
2
3
4

on peut déterminer la position d'une reine par un numéro de ligne et un numéro de colonne. Ainsi, une première modélisation consiste à associer à chaque reine i deux variables Li et Ci correspondant respectivement à la ligne et la colonne sur laquelle placer la reine. Les contraintes spécifient alors que les reines doivent être sur des lignes différentes, des colonnes différentes et des diagonales différentes. Notons pour cela que lorsque 2 reines sont sur une même diagonale montante, la somme de leurs numéros de ligne et de colonne est égale, tandis que lorsqu'elles sont sur une même diagonale descendante, la différence de leurs numéros de ligne et de colonne est égale. On en déduit le CSP suivant :

Les contraintes Clig et Ccol sont des contraintes binaires ; les contraintes Cdm et Cdd sont des contraintes quaternaires. L'énumération de toutes ces contraintes est ici un peu fastidieuse. On peut tout aussi bien les définir de la façon suivante :

On aurait également pu utiliser une contrainte globale pour exprimer le fait que toutes les variables d'un ensemble doivent avoir des valeurs différentes : Clig = toutesDiff({L1,L2,L3,L4}) et Ccol = toutesDiff({C1,C2,C3,C4}).

Une solution du problème des 4 reines, pour cette première modélisation, est

A = {(C1,1), (L1,2), (C2,2), (L2,4), (C3,3), (L3,1), (C4,4), (L4,3)}
ou autrement dit, la première reine est placée colonne 1 ligne 2, la deuxième, colonne 2 ligne 4, la troisième, colonne 3 ligne 1 et la quatrième, colonne 4 ligne 3.

Les reines / Deuxième modélisation

Dans la mesure où l'on sait dès le départ qu'il y aura une reine et une seule sur chaque colonne de l'échiquier, le problème peut se résumer à déterminer sur quelle ligne se trouve la reine placée sur la colonne i. Par conséquent, une deuxième modélisation consiste à associer une variable Xi à chaque colonne i de telle sorte que Xi désigne le numéro de ligne sur laquelle placer la reine de la colonne i. Notons que pour cette deuxième modélisation, on a été obligé de "réfléchir" un peu pour introduir dans la modélisation une déduction (il y a une seule reine par colonne) qui, on l'espère, va faciliter le travail de la machine. Le CSP correspondant à cette deuxième modélisation est le suivant : Une solution du problème des 4 reines, pour cette deuxième modélisation, est
A = {(X1,2), (X2,4), (X3,1), (X4,3)}
ou autrement dit, la reine de la colonne 1 est placée sur la ligne 2, celle de la colonne 2, ligne 4, celle de la colonne 3, ligne 1 et celle de la colonne 4, ligne 3.

Les reines / Troisième modélisation

Une autre façon, radicalement opposée, de modéliser le problème consiste à choisir comme variables non pas les positions des reines, mais les états des cases de l'échiquier : on associe une variable à chacune des 16 cases de l'échiquier (on notera Xij la variable associée à la case située ligne i et colonne j) ; chaque variable peut prendre pour valeur 0 (s'il n'y a pas de reine sur la case) ou 1 (s'il y a une reine sur la case) ; les contraintes spécifient qu'il ne peut y avoir plusieurs reines sur une même ligne, une même colonne ou une même diagonale. Le CSP correspondant à cette troisième modélisation est le suivant : Une solution du problème des 4 reines, pour cette troisième modélisation, est
A = {(X11,0), (X12,1), (X13,0), (X14,0), (X21,0), (X22,0), (X23,0), (X24,1), (X31,1), (X32,0), (X33,0), (X34,0), (X41,0), (X42,0), (X43,1), (X44,0)}
ou, autrement dit, la case ligne 1 colonne 1 (X11) est vide, la case ligne 1 colonne 2 (X12) est occupée, ...

Les reines / Discussion

La question (légitime) que l'on peut maintenant se poser est : "Quelle est la meilleure modélisation ?"

Il n'y a pas une seule réponse à cette question... mais au moins trois :

  1. Celle qui modélise le mieux la réalité du problème. De ce point de vue, les 3 modélisations sont équivalentes.
  2. Celle qui est la plus facile à trouver. De ce point de vue, la première modélisation est probablement plus "simple"... même si cela est subjectif !
  3. Celle qui permettra de résoudre le problème le plus efficacement. On ne peut vraiment répondre à cette question qu'à partir du moment où l'on sait comment un CSP est résolu (ce que vous ne tarderez pas à savoir ...). Intuitivement, on se doute que la deuxième modélisation devrait être meilleure que la première dans la mesure où elle prend en compte le fait que les reines sont sur des colonnes différentes par la définition même des variables, sans avoir à poser de contrainte. On verra que "l'espace de recherche" de cette deuxième modélisation est plus petit que celui de la première.

Généralisation à n reines

On peut généraliser le problème au placement de n reines sur un échiquier comportant n colonnes et n lignes. Par exemple, la deuxième modélisation devient :

4 - Un deuxième exemple : les mariages stables

4.1 - Description du problème :

Une agence matrimoniale aux méthodes modernes souhaite proposer à ses clients des mariages "stables". Elle demande pour cela à chacun de ses membres de classer les membres du sexe opposé, établissant de la sorte une liste de préférences. Pour tenir compte au mieux des désirs des clients, ces listes peuvent être incomplètes, c'est-à-dire que si Paul ne veut à aucun prix être marié à Isabelle, il peut ne pas la classer (il ne la met pas dans sa liste de préférences). Par ailleurs, on peut mettre dans une liste des "ex aequo" : dans le cas où un indécis n'arrive pas à trancher entre plusieurs personnes qui lui semblent également attirantes, il peut les classer ex aequo. Pour simplifier, on supposera que l'on a autant d'hommes que de femmes.

Il s'agit alors, à partir de ces listes de préférences éventuellement incomplètes et avec des ex aequo, de former des couples stables. Par stable, on entend que personne ne soit soumis à la tentation de divorcer pour trouver mieux ailleurs : si Roméo est marié à Isabelle, et Paul à Juliette, et si à la fois Roméo préfère Juliette à Isabelle et Juliette préfère Roméo à Paul, alors ces mariages ne seront pas stables car Roméo et Juliette seront tentés de divorcer pour pouvoir convoler ensemble.

Dans l'agence matrimoniale qui nous intéresse plus particulièrement, il y a 6 hommes (que l'on appellera 1, 2, 3, 4, 5 et 6 pour préserver leur anonymat), et 6 femmes (que l'on appellera 7, 8, 9, 10, 11 et 12 pour les mêmes raisons). Leurs préférences exprimées sont les suivantes :

Les classements des hommes :
  • 1 préfère 8, puis (12 et 10 ex aequo) ;
  • 2 préfère (8 et 11 ex aequo), puis 12 ;
  • 3 préfère 7, puis 9, puis 12 ;
  • 4 préfère 12, puis 9 ;
  • 5 préfère 8, puis 7, puis 11 ;
  • 6 préfère 12, puis (10 et 8 ex aequo), puis 11, puis 7.
 		Les classements des femmes :
  • 7 préfère (5 et 3 ex aequo), puis 6 ;
  • 8 préfère 2, puis, 5, puis 1, puis 6 ;
  • 9 préfère (3 et 4 ex aequo) ;
  • 10 préfère 6, puis 1 ;
  • 11 préfère 5, puis 2, puis 6 ;
  • 12 préfère 1, puis (4 et 6 ex aequo), puis 2, puis 3.

Au vu de ces préférences exprimées, les mariages de 3 avec 9 et de 6 avec 7 ne sont pas stables car 3 préfère 7 à 9 tandis que 7 préfère 3 à 6 de telle sorte que 3 et 7 seront tentés de divorcer pour se remarier ensemble. En revanche, une solution stable consisterait, par exemple, à marier 1 avec 10, 2 avec 8, 3 avec 7, 4 avec 9, 5 avec 11 et 6 avec 12.

Remarque : ce problème peut sembler quelque peu artificiel, mais si vous remplacez les hommes par des étudiants en recherche de stage, et les femmes par des entreprises recherchant des stagiaires, vous obtenez un problème plus réaliste...

4.2 - Modélisation sous la forme d'un CSP :

Pour modéliser ce problème sous la forme d'un CSP, il s'agit une fois de plus d'identifier l'ensemble X des variables, les domaines de valeurs D des variables, et les contraintes C entre les variables. Ici, on souhaite déterminer qui se marie avec qui. Pour exprimer cela, on peut associer à chaque homme i une variable épouse-de-i qui représente son épouse, et à chaque femme j une variable mari-de-j qui représente son mari. Néanmoins, sachant que l'on peut retrouver le mari d'une femme en cherchant l'homme dont elle est l'épouse, on peut ne garder comme variable que les épouses :
X = {épouse-de-1, épouse-de-2, épouse-de-3, épouse-de-4, épouse-de-5, épouse-de-6}
Pour chaque variable épouse-de-i, le domaine associé contient l'ensemble des femmes qui sont classées par i et qui ont classé i :
D(épouse-de-1) = {8,10,12}
D(épouse-de-2) = {8,11,12}
D(épouse-de-3) = {7,9,12}
D(épouse-de-4) = {9,12}
D(épouse-de-5) = {7,8,11}
D(épouse-de-6) = {7,8,10,11,12}
Enfin, les contraintes sont de deux types : C = {C1, C2} Une solution du problème des mariages stables modélisé par ce CSP est :
{ (épouse-de-1,10), (épouse-de-2,8), (épouse-de-3,7), (épouse-de-4,9), (épouse-de-5,11), (épouse-de-6,12) }