Distributed constraint optimization

Distributed constraint optimization (DCOP) is the distributed analogue to constraint optimization. A DCOP is a problem in which a group of agents must distributedly choose values for a set of variables such that the cost of a set of constraints over the variables is either minimized or maximized.

Definitions

DCOP

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

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

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

Context

A Context is a variable assignment for a DCOP. This can be thought of as a function mapping variables in the DCOP to their current values:

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

Note that a context is essentially a partial solution and need not contain values for every variable in the problem; therefore, $t(v_{i})\mapsto \emptyset$ implies that the agent $\alpha (v_{i})$ has not yet assigned a value to variable $v_{i}$. Given this representation, the "domain" (i.e., the set of input values) of the function f can be thought of as the set of all possible contexts for the DCOP. Therefore, in the remainder of this article we may use the notion of a context (i.e., the $t$ function) as an input to the $f$ function.

Example problems

Distributed Graph Coloring

The graph coloring problem is as follows: given a graph $G=\langle N,E\rangle$ and a set of colors $C$, assign each vertex, $n\in N$, a color, $c\in C$, such that the number of adjacent vertices with the same color is minimized.

As a DCOP, 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 $|C|$ (there is one domain value for each possible color). For each vertex $n_{i}\in N$, create a variable in the DCOP $v_{i}\in V$ with domain $D_{i}=C$. For each pair of adjacent vertices $\langle n_{i},n_{j}\rangle \in E$, create a constraint of cost 1 if both of the associated variables are assigned the same color:

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

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

Distributed Multiple Knapsack Problem

The Distributed Multiple- variant of the Knapsack problem is as follows: given a set of items of varying volume and a set of knapsacks of varying capacity, assign each item to a knapsack such that the amount of overflow is minimized. Let $I$ be the set of items, $K$ be the set of knapsacks, $s:I\rightarrow \mathbb {N}$ be a function mapping items to their volume, and $c:K\rightarrow \mathbb {N}$ be a function mapping knapsacks to their capacities.

To encode this problem as a DCOP, for each $i\in I$ create one variable $v_{i}\in V$ with associated domain $D_{i}=K$. Then for all possible context $t$:

$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}}$

where $r(t,k)$ is a function such that

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

Algorithms

Algorithm Name	Year Introduced	Complexity	Correctness/ Completeness	Implementations
NCBB No-Commitment Branch and Bound	2006	Memory: Polynomial (or any-space)	Proven	Reference Implementation: not publicly released DCOPolis (GNU LGPL)
DPOP Distributed Pseudotree Optimization Procedure	2004	Memory: Exponential	Proven	Reference Implementation: FRODO (free but proprietary) DCOPolis (GNU LGPL)
OptAPO Asynchronous Partial Overlay	2004	Memory: Polynomial	Proven, but proof of completeness has been challenged	Reference Implementation: OptAPO DCOPolis (GNU LGPL); In Development
Adopt Asynchronous Backtracking	2003	Memory: Polynomial (or any-space)	Proven	Reference Implementation: Adopt DCOPolis (GNU LGPL)

See also

• Distributed Constraint Satisfaction Problem (DisCSP)