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 a set of ${\displaystyle |V|^{2}}$  cost functions, one for each pair of the variables, such that ${\displaystyle f_{ij}:D_{i}\times D_{j}\rightarrow \mathbb {N} \cup \infty }$ . In other words, for all pairs of variables there exists a cost function that maps every possible value assignment of the variables to a cost. These functions can also be thought of as binary 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.
• ${\displaystyle \sigma }$  is a function ${\displaystyle \sigma :F\rightarrow \mathbb {N} \cup \infty }$  that aggregates the individual costs. 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.