MAXSUM

MaxSum: Belief-propagation DCOP algorithm

Max-Sum [FRPJ08] is an incomplete inference-based DCOP algorithm.

This is a synchronous implementation of Max-Sum, where messages are sent and received in cycles. For an asynchronous version, see AMaxSum.

Algorithm Parameters

• damping: float, default = 0.5

  Amount of damping [0-1].

• damping_nodes: “vars”, “factors”, “both” or “none”, default = “both”

  Nodes that apply damping to messages.

• stability: float, default = 0.1 (STABILITY_COEFFICIENT)

  Stability detection coefficient

• noise: float, default = 0.01

  Noise level for variables

• start_messages: “leafs”, “leafs_vars”, “all”, default = “leafs”

  Nodes that initiate messages.

FIXME: add support for stop_cycle

Example

pydcop solve -algo maxsum  \
  --algo_param stop_cycle:30 \
 -d adhoc graph_coloring_csp.yaml

FIXME: add results

See also

A-Max-Sum: an asynchronous implementation of Max-Sum.