Optimisation sous contraintes distribuée

Un DCOP peut être défini comme un tuple ${\displaystyle \langle A,V,{\mathfrak {D}},f,\alpha ,\eta \rangle }$, où:

• ${\displaystyle A}$ est un ensemble d' agents ;
• ${\displaystyle V}$ est un ensemble de variables, ${\displaystyle \{v_{1},v_{2},\cdots ,v_{|V|}\}}$ ;
• ${\displaystyle {\mathfrak {D}}}$ est un ensemble des domaines, ${\displaystyle \{D_{1},D_{2},\ldots ,D_{|V|}\}}$, où chaque ${\displaystyle D\in {\mathfrak {D}}}$ est un ensemble fini contenant les valeurs qui peuvent être affectées à la variable vi associée au domaine Di;
• ${\displaystyle f}$ est une fonction [1] - [2] ${\displaystyle f:\bigcup _{S\in {\mathfrak {P}}(V)}\sum {v_{i}\in S}\left(\{v_{i}\}\times D_{i}\right)\rightarrow \mathbb {R} \cup \{\bot \}}$ qui associe chaque affectation de variable possible à un coût ou une utilité. Cette fonction peut également être considérée comme définissant des contraintes entre les variables, mais les variables ne doivent pas être hermitiennes;
• ${\displaystyle \alpha }$ est une fonction ${\displaystyle \alpha :V\rightarrow A}$ qui associe les variables à l'agent qui leur est associé. ${\displaystyle \alpha (v_{i})\mapsto a_{j}}$ implique que l'agent ${\displaystyle a_{j}}$ a la responsabilité d'attribuer sa valeur à la variable ${\displaystyle v_{i}}$ . Notez qu'il n'est pas forcément vrai que ${\displaystyle \alpha }$ est une injection ou une surjection (i.e. un agent peut être responsable de plusieurs variables, ou d'aucune mais une variable n'est sous la responsabilité que d'un seul agent); et
• ${\displaystyle \eta }$ est un opérateur qui agrège l'ensemble des fonctions ${\displaystyle f}$ de coût ou d'utilité pour toutes les valeurs possibles (i.e. respectant leurs domaines) des variables. Cette fonction est généralement une somme: ${\displaystyle \eta (f)\mapsto \sum _{s\in \bigcup _{S\in {\mathfrak {P}}(V)}\sum {v_{i}\in S}\left(\{v_{i}\}\times D_{i}\right)}f(s)}$ .

L'objectif d'un DCOP est que chaque agent attribue des valeurs aux variables qui lui sont associées afin que l'affectation globale de l'ensemble des variables minimise (ou de maximise dans le cas des fonctions d'utilité) ${\displaystyle \eta (f)}$.

Un contexte est une affectation d'une variable dans un DCOP. Il peut être considéré comme une fonction associant les variables du DCOP à leurs valeurs actuelles:

${\displaystyle t:V\rightarrow (D\in {\mathfrak {D}})\cup \{\emptyset \}.}$

Notons qu'un contexte est essentiellement une solution partielle et n'a pas besoin de contenir des valeurs pour chaque variable du problème; on note donc ${\displaystyle t(v_{i})\mapsto \emptyset }$ lorsque l'agent ${\displaystyle \alpha (v_{i})}$ n'a pas encore attribué de valeur à la variable ${\displaystyle v_{i}}$ . Compte tenu de cette représentation, le "domaine" (c'est-à-dire l'ensemble des valeurs d'entrée) de la fonction ${\displaystyle f}$ peut être considéré comme l'ensemble de tous les contextes possibles pour le DCOP. Par conséquent, dans le reste de cet article, on utilisera la notion de contexte (c'est-à-dire la fonction ${\displaystyle t}$) comme entrée de la fonction ${\displaystyle f}$.

Le problème de coloration de graphe est le suivant: étant donné un graphe ${\displaystyle G=\langle N,E\rangle }$ et un ensemble de couleurs ${\displaystyle C}$, on cherche à attribuer à chaque sommet du graphe ${\displaystyle n\subset N}$, une couleur, ${\displaystyle c\leq C}$ de manière que le nombre de sommets adjacents de même couleur soit minimisé.

Dans la formalisation DCOP du problème, on considère qu'il y a un agent par sommet, et qu'il a la responsabilité de décider de la couleur associée à ce sommet. Chaque agent a une seule variable (le sommet dont il est responsable) dont le domaine associé est l'ensemble des couleurs, de cardinalité ${\displaystyle |C|}$. Pour chaque sommet ${\displaystyle n_{i}\leq N}$, on crée dans le DCOP une variable ${\displaystyle v_{i}\in V}$ avec pour domaine domaine ${\displaystyle D_{i}=C}$ . Pour chaque paire de sommets adjacents ${\displaystyle \langle n_{i},n_{j}\rangle \in E}$, on ajoute une contrainte de coût 1 si les deux variables associées ont la même couleur:

${\displaystyle (\forall c\subseteq C:f(\langle v_{i},c\rangle ,\langle v_{j},c\rangle )\mapsto 1).}$

L'objectif est ici de minimiser ${\displaystyle \eta (f)}$ .

Le problème du sac à dos multiple est une variante du problème du sac à dos où: étant donné un ensemble d'objets de volume variable et un ensemble de sacs à dos de capacité variable, on cherche à attribuer à chaque objet à un sac à dos de manière à minimiser le débordement des sacs. Soit ${\displaystyle I}$ l'ensemble des objets, ${\displaystyle K}$ l'ensemble des sacs à dos, ${\displaystyle s:I\rightarrow \mathbb {N} }$ une fonction qui associe les éléments à leur volume, et ${\displaystyle c:K\rightarrow \mathbb {N} }$ une fonction associant les sacs à dos à leurs capacités.

Pour formaliser ce problème sous la forme d'un DCOP, on crée pour chaque ${\displaystyle i\in I}$ une variable ${\displaystyle v_{i}\in V}$ dont le domaine est ${\displaystyle D_{i}=K}$ . Puis pour tous les contextes possibles ${\displaystyle t}$ :

${\displaystyle f(t)\mapsto \sum _{k\in K}{\begin{cases}0&r(t,k)\leq c(k),\\r(t,k)-c(k)&{\text{otherwise}},\end{cases}}}$

où ${\displaystyle r(t,k)}$ est une fonction telle que

${\displaystyle r(t,k)=\sum _{v_{i}\in t^{-1}(k)}s(i).}$