Distributed constraint optimization

Distributed constraint optimization (DCOP) is the distributed analogue to constraint optimization.

Definition

A DCOP can be defined as a tuple ${\displaystyle \langle A,V,{\mathcal {D}},f,\alpha ,\sigma \rangle }$ , where:

• ${\displaystyle A}$  is a set of agents;
• ${\displaystyle V}$  is a set of variables, ${\displaystyle \{v_{1},v_{2},\ldots ,v_{|V|}\}}$ ;
• ${\displaystyle {\mathcal {D}}}$  is a set of domains, ${\displaystyle \{D_{1},D_{2},\ldots ,D_{|V|}\}}$ , where each ${\displaystyle D\in {\mathcal {D}}}$  is a finite set containing the values to which its associated variable my be assigned;
• ${\displaystyle f}$  is function ${\displaystyle f:{\mathcal {P}}({\mathcal {D}})\rightarrow \mathbb {N} \cup \infty }$  (where "${\displaystyle {\mathcal {P}}({\mathcal {D}})}$ " denotes the power set of ${\displaystyle {\mathcal {D}}}$ ) that maps every possible grouping of variable assignments to a cost. This function can also be thought of as defining constraints between variables;
• ${\displaystyle \alpha }$  is a function ${\displaystyle \alpha :V\rightarrow A}$  mapping variables to their associated agent. ${\displaystyle \alpha (v_{i})\mapsto a_{j}}$  implies that it is agent ${\displaystyle a_{j}}$ 's responsibility to assign the value of variable ${\displaystyle v_{i}}$ . Note that it is not necessarily true that ${\displaystyle \alpha }$  is either an injection or surjection; and
• ${\displaystyle \sigma }$  is an operator ${\displaystyle \sigma :f\rightarrow \mathbb {N} \cup \infty }$  that aggregates all of the individual costs for all possible variable assignments. This is usually accomplished through summation of the costs.

The objective of a DCOP is to have each agent assign values to its associated variables in order to either minimize or maximize ${\displaystyle \sigma (f)}$  for a given assignment of the variables.

Example

Consider 3-coloring a graph; there is one agent per vertex that is assigned to decide the associated color. Each agent has a single variable whose associated ___domain is of cardinality 3 (there is one ___domain value for each possible color). Given the graph  , the following would be its representation as a DCOP for solving the 3-coloring problem:

• ${\displaystyle A=\{a_{1},a_{2},\ldots ,a_{6}\}}$ 
• ${\displaystyle V=\{v_{1},v_{2},\ldots ,v_{6}\}}$ 
• ${\displaystyle {\mathcal {D}}=\{D_{1},D_{2},\ldots ,D_{6}\}}$ , where each ${\displaystyle D\in {\mathcal {D}}=\{{\mbox{Red}},{\mbox{Green}},{\mbox{Blue}}\}}$ 
• ${\displaystyle f}$  returns 0 in all but the following cases:
  • ${\displaystyle f(D_{1}=D_{2})=\infty }$  (i.e. whenever ${\displaystyle D_{1}}$  equals the value of ${\displaystyle D_{2}}$ , the cost is infinite)
  • ${\displaystyle f(D_{1}=D_{5})=\infty }$ 
  • ${\displaystyle f(D_{5}=D_{2})=\infty }$ 
  • ${\displaystyle f(D_{2}=D_{3})=\infty }$ 
  • ${\displaystyle f(D_{3}=D_{4})=\infty }$ 
  • ${\displaystyle f(D_{4}=D_{5})=\infty }$ 
  • ${\displaystyle f(D_{4}=D_{6})=\infty }$ 
• ${\displaystyle \sigma =\sum _{{\mathcal {P}}({\mathcal {D}})}f}$ 

The objective, then, is to minimize ${\displaystyle \sigma (f)}$ .