Content deleted Content added
Finished the graph coloring example. |
Added the distributed multiple knapsack problem example. |
||
Line 26:
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 $D_i = C$. 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===
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 <math>I</math> be the set of items, <math>K</math> be the set of knapsacks, <math>s : I \rightarrow \mathbb{N}</math> be a function mapping items to their volume, and <math>c : K \rightarrow \mathbb{N}</math> be a function mapping knapsacks to their capacities.
To encode this problem as a DCOP, for each <math>i \in I</math> create one variable <math>v_i \in V</math> with associated ___domain <math>D_i = K</math>. Then for all possible context <math>t</math>:<center><math>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}</math></center>where <math>r(t,k)</math> is a function such that<center><math>r(t,k) = \sum_{v_i \in t^{-1}(k)} s(i).</math></center>
==Algorithms==
==Notes==
| |||