Getting started

This small tutorial will guide you to solve your first DCOP using pyDCOP.

Solving your first DCOP

Once you have installed pyDCOP (and activated the python venv you have installed it in), create a text file graph_coloring.yaml with following content:

name: graph coloring
objective: min

domains:
  colors:
    values: [R, G]

variables:
  v1:
    domain: colors
  v2:
    domain: colors
  v3:
    domain: colors

constraints:
    pref_1:
      type: extensional
      variables: v1
      values:
        -0.1: R
        0.1: G

    pref_2:
      type: extensional
      variables: v2
      values:
        -0.1: G
        0.1: R

    pref_3:
      type: extensional
      variables: v3
      values:
        -0.1: G
        0.1: R

    diff_1_2:
      type: intention
      function: 10 if v1 == v2 else 0

    diff_2_3:
      type: intention
      function: 10 if v3 == v2 else 0

agents: [a1, a2, a3, a4, a5]

You don’t need for the moment to understand everything in this file, it’s enough to know that it represents a graph coloring problem, modeled as a DCOP with 3 variables (this example is taken from [FRPJ08] ).

Now you can simply run the following command to solve this DCOP with the DPOP algorithm:

pydcop solve --algo dpop graph_coloring.yaml

This should output a result simular to this:

{
  // Rather long list of information, not included here ....
  "assignment": {
    "v1": "R",
    "v2": "G",
    "v3": "R"
  },
  "cost": -0.1,
  "cycle": 1,
  "msg_count": 4,
  "msg_size": 8,
  "status": "FINISHED",
  "time": 0.008432154994807206,
  "violation": 0
}

Congratulations, you have solved your first DCOP using pyDCOP !!

Of course, you can solve it with any other DCOP algorithm implemented by pyDCOP. Some algorithms have no default termination condition, in this case you can stop the execution with CTRL+C or use the --timeout option:

pydcop --timeout 3 solve --algo mgm graph_coloring.yaml

You may notice that with this command the assignment in the result is not always the same and not always the result we found using DPOP. This is because MGM is a local search algorithm, which can be trapped in a local minimum. On the other hand DPOP is a complete algorithm and will always return the optimal assignment (if your problem is small enough to use DPOP on it !).

Now that you have run your first DCOP, you can head to the next tutorial to learn how to analyse the results.