Distributed constraint optimization: Difference between revisions

Revision as of 15:15, 27 April 2007

Revision as of 15:41, 27 April 2007

Line 20:

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:<center><math>t : V \rightarrow (D \in \mathcal{D}) \cup \{\emptyset\}.</math></center> Note that a context is essentially a partial solution and need not contain values for <em>every</em> variable in the problem; therefore, <math>t(v_i) \mapsto \emptyset</math> implies that the agent <math>\alpha(v_i)</math> has not yet assigned a value to variable <math>v_i</math>. Given this representation, the "[[Domain_(mathematics)|___domain]]" (<i>i.e.</i>, the set of input values) of the function <code>f</code> 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>i.e.</i>, the <math>t</math> function) as an input to the <math>f</math> function.

==Example problems==

==Examples==

===Distributed Graph Coloring===

The [[Graph coloring|graph coloring]] problem is as follows: given a [[Graph_(mathematics)|graph]] <math>G = \langle N, E \rangle</math> and a set of colors <math>C</math>, assign each [[Vertex_(graph_theory)|vertex]], <math>n\in N</math>, a color, <math>c\in C</math>, 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]] <math>|C|</math> (there is one ___domain value for each possible color). For each vertex <math>n_i \in N</math>, create a variable in the DCOP <math>v_i \in V</math> with ___domain $<math>D_i = C$</math>. For each pair of adjacent vertices <math>\langle n_i, n_j \rangle \in E</math>, create a constraint of cost 1 if both of the associated variables are assigned the same color: <center><math>(\forall c \in C : f(\langle v_i, c \rangle, \langle v_j, c \rangle ) \mapsto 1).</math></center>The objective, then, is to minimize <math>\sigma(f)</math>.

===Distributed Multiple Knapsack Problem===

Line 122:

|}

==Notes and references==

<references/>