pydcop.algorithms.dpop

DPOP: Dynamic Programming Optimization Protocol

Dynamic Programming Optimization Protocol is an optimal, inference-based, dcop algorithm implementing a dynamic programming procedure in a distributed way [PF04].

DPOP works on a Pseudo-tree, which can be built using the distribute command (and is automatically built when using the solve command).

This algorithm has no parameter.

Example

pydcop -algo dpop graph_coloring_eq.yaml
class DpopAlgo(comp_def: ComputationDef)

DPOP: Dynamic Programming Optimization Protocol

When running this algorithm, the DFS tree must be already defined and the children, parents and pseudo-parents must be known.

In DPOP: * A computation represents, and select a value for, one variable. * A constraint is managed (i.e. referenced) by a single computation object:

this means that, when building the computations, each constraint must only be passed as argument to a single computation.

  • A constraint must always be managed by the lowest node in the DFS tree that the relation depends on (which is especially important for non-binary relation). The pseudo-tree building mechanism already takes care of this.

DPOP computations support two kinds of messages: * UTIL message:

sent from children to parent, contains a relation (as a multi-dimensional matrix) with one dimension for each variable in our separator.

  • VALUE messages : contains the value of the parent of the node and the values of all variables that were present in our UTIl message to our parent (that is to say, our separator) .

Parameters:

  • variable (Variable) – The Variable object managed by this algorithm

  • parent (variable name (str)) – the parent for this node. A node has at most one parent but may have 0-n pseudo-parents. Pseudo parent are not given explicitly but can be deduced from the constraints and children (if the union of the constraints’ scopes contains a variable that is not a children, it must necessarily be a pseudo-parent). If the variable shares a constraints with its parent (which is the most common case), it must be present in the relation arg.

  • children (name of children variables (list of str)) – the children variables of the variable argument, in the DFS tree

  • constraints (List of Constraints) – constraints managed by this computation. These relations will be used when calculating costs. It must depends on the variable arg. Unary relation are also supported. Remember that a relation must always be managed by the lowest node in the DFS tree that the relation depends on (which is especially important for non-binary relation).

comp_def: ComputationDef

computation definition, gives the algorithm name (must be dpop) and the mode (min or max)

footprint()

Return the footprint of the computation.

The footprint is used by many distribution methods.

Notes

This methods should NOT be overwritten when subclassing VariableComputation, instead, you should provide a computation_memory function at module-level in your algorithm. This method computes the footprint from a ComputationNode, which is required to for bootstrap distributions, where the distribution is computed before instanciating the computation objects.

This module level function must have the following signature:

> computation_memory(computation: ComputationNode) -> float:

Returns:

The footprint of the computation.

Return type:

float

on_start()

Called when starting the computation.

This method is meant to be overwritten in subclasses.

select_value_and_finish(value, cost)

Select a value for this variable.

DPOP is not iterative, once we have selected our value the algorithm is finished for this computation.

Parameters:

  • value (any (depends on the domain)) – the selected value

  • cost (float) – the local cost for this value

class DpopMessage(msg_type, content)
property size

Returns the size of the message.

You should overwrite this methods in subclasses, will be used when computing the communication load of an algorithm and by some distribution methods that optimize the distribution of computation for communication load.

Returns:

size

Return type:

int