Distributed constraint optimization

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

Uses your system voice; voice and rate in settings.

Snapshot

≈ 7 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

Distributed constraint optimization (DCOP or DisCOP) 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 minimized.

Distributed Constraint Satisfaction is a framework for describing a problem in terms of constraints that are known and enforced by distinct participants (agents). The constraints are described on some variables with predefined domains, and have to be assigned to the same values by the different agents.

Problems defined with this framework can be solved by any of the algorithms that are designed for it. The framework was used under different names in the 1980s. The first known usage with the current name is in 1990.

DCOP

The main ingredients of a DCOP problem are agents and variables. Importantly, each variable is owned by an agent; this is what makes the problem distributed. Formally, a DCOP is a tuple \langle A, V, \mathfrak{D}, f, \alpha, \eta \rangle , where: A is the set of agents, \{a_1, \dots, a_ \} .

V is the set of variables, \{v_1, v_2, \dots, v_ \} . \mathfrak{D} is the set of variable-domains, {{nowrap| \{D_1, D_2, \dots, D_ \} ,}} where each D_j \in \mathfrak{D} is a finite set containing the possible values of variable v_j . If D_j \in \mathfrak{D} contains only two values (e.g. 0 or 1), then v_j is called a binary variable. f is the cost function. It is a function f : \bigcup_{S \subseteq V} \times_{v_j \in S} D_j \to \R that maps every possible partial assignment to a cost.

Usually, only few values of f are non-zero, and it is represented as a list of the tuples that are assigned a non-zero value. Each such tuple is called a constraint. Each constraint C in this set is a function f_C: D_1\times\cdots\times D_k \to \R assigning a real value to each possible assignment of the variables.

Some special kinds of constraints are: Unary constraints - constraints on a single variable, i.e., f_C: D_j \to \R for some v_j\in V . Binary constraints - constraints on two variables, i.e., f_C: D_{j_1} \times D_{j_2} \to \R for some \alpha is the ownership function. It is a function \alpha: V \to A mapping each variable to its associated agent. \alpha(v_j) \mapsto a_i means that variable v_j "belongs" to agent a_i . This implies that it is agent a_i 's responsibility to assign the value of variable v_j . Note that \alpha is not necessarily an injection, i.e., one agent may own more than one variables.

It is also not necessarily a surjection, i.e., some agents may own no variables. \eta is the objective function. It is an operator that aggregates all of the individual f costs for all possible variable assignments.

This is usually accomplished through summation: \eta(f) \mapsto \sum_{s \in \bigcup_{S \subseteq V} \times_{v_j \in S} D_j} 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 \eta(f) for a given assignment of the variables.

Assignments

A value assignment is a pair (v_j, d_j) where d_j is an element of the domain D_j . A partial assignment is a set of value-assignments where each v_j appears at most once. It is also called a context. This can be thought of as a function mapping variables in the DCOP to their current values: t : V \to (D \in \mathfrak{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" (that is, 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.

A full assignment is an assignment in which each v_j appears exactly once, that is, all variables are assigned. It is also called a solution to the DCOP. An optimal solution is a full assignment in which the objective function \eta(f) is optimized (i.e., maximized or minimized, depending on the type of problem).

Example problems

Various problems from different domains can be presented as DCOPs.

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\subset N , a color, c \leq 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 \leq N , there is a variable v_i \in V with domain D_i = C . For each pair of adjacent vertices \langle n_i, n_j \rangle \in E , there is a constraint of cost 1 if both of the associated variables are assigned the same color: (\forall c \subseteq C : f(\langle v_i, c \rangle, \langle v_j, c \rangle ) \mapsto 1).

The objective, then, is to minimize \eta(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 \to \N be a function mapping items to their volume, and c : K \to \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 contexts 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) represents the total weight assigned by context t to knapsack k : r(t,k) = \sum_{v_i \in t^{-1}(k)} s(i).

Asymmetric DCOP

An asymmetric DCOP is an extension of DCOP in which the cost of each constraint may be different for different agents. Some example applications are: Event scheduling: agents who attend the same event might derive different values from it. Smart grid: the increase in price of electricity in loaded hours may be different agents.

One way to represent an ADCOP is to represent the constraints as functions: f_C: D_1\times\dots\times D_k \to \R^k Here, for each constraint there is not a single cost but a vector of costs - one for each agent involved in the constraint. The vector of costs is of length k if each variable belongs to a different agent; if two or more variables belong to the same agent, then the vector of costs is shorter - there is a single cost for each involved agent, not for each variable.

See also

Constraint satisfaction problem Distributed algorithm Distributed algorithmic mechanism design

Books and surveys

A chapter in an edited book. See Chapters 1 and 2; downloadable free online.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1373259947 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

16 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.