pydcop.algorithms.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.

class MaxSumFactorComputation(comp_def: ComputationDef)
footprint() → float

The footprint of the computation.

A DCOP computation has a footprint, which represents the amount of memory this computation requires to run. This depends on the algorithm used and thus must be overwritten in subclasses. This footprint is used when distributing computation on agents, to ensure that agents only host computation they can run.

Returns:

the footprint

Return type:

float

on_new_cycle(messages, cycle_id) → List | None

Called when switching to a new cycle.

This method must be overridden in derived classes, this is where you write the logic of your synchronous algorithm. It is automatically called when all messages have been received for the current cycle and should be handled. When handling these messages, the computation will generally also send messages to some of its neighbors; this can be achieved either by using post_msg or by returning the list of messages that must be sent for this cycle. Notice that these messages will be delivered in the next cycle.

Notes

You are only allowed to send at most one message to any given neighbor in a cycle. If you send several messages to the same neighbor, a ComputationException will be raised by this neighbor in the next cycle, when receiving them.

Parameters:

  • messages (dict) – all the messages received for this cycle (i.e. that have been set by neighbors during the previous cycle). The keys of the dict are the sender of the message, the values are tuple (message, time).

  • cycle_id (int) – id for this cycle

Returns:

messages – a list of tuples (target, message) with the messages to be sent to neighbors for this cycle (which they will receive at the next cycle).

Return type:

list of None

on_start()

Called when starting the computation.

This method is meant to be overwritten in subclasses.

class MaxSumMessage(costs: Dict)
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

class MaxSumVariableComputation(comp_def: ComputationDef)
on_new_cycle(messages, cycle_id) → List | None

Called when switching to a new cycle.

This method must be overridden in derived classes, this is where you write the logic of your synchronous algorithm. It is automatically called when all messages have been received for the current cycle and should be handled. When handling these messages, the computation will generally also send messages to some of its neighbors; this can be achieved either by using post_msg or by returning the list of messages that must be sent for this cycle. Notice that these messages will be delivered in the next cycle.

Notes

You are only allowed to send at most one message to any given neighbor in a cycle. If you send several messages to the same neighbor, a ComputationException will be raised by this neighbor in the next cycle, when receiving them.

Parameters:

  • messages (dict) – all the messages received for this cycle (i.e. that have been set by neighbors during the previous cycle). The keys of the dict are the sender of the message, the values are tuple (message, time).

  • cycle_id (int) – id for this cycle

Returns:

messages – a list of tuples (target, message) with the messages to be sent to neighbors for this cycle (which they will receive at the next cycle).

Return type:

list of None

on_start() → None

Called when starting the computation.

This method is meant to be overwritten in subclasses.

approx_match(costs: Dict[Any, float], prev_costs: Dict[Any, float], stability_coef: float) → bool

Check if a cost message match the previous message.

Costs are considered to match if the variation is bellow STABILITY_COEFF.

Parameters:

  • costs (Dict[val, cost]) – Cost information as a dictionary mapping values to costs

  • prev_costs (Dict[val, cost]) – Previous costs as a dict val -> cost

  • stability_coef (float) – If the difference between the two is less than this value, the costs are considered to match.

Returns:

bool

Return type:

True if costs match prev_costs

communication_load(src: FactorComputationNode | VariableComputationNode, target: str) → float

The communication cost of an edge between a variable and a factor.

Parameters:

  • src (VariableComputationNode) – The ComputationNode for the source variable.

  • target (str) – the name of the other variable src is sending messages to

Returns:

the size of messages between computation and target.

Return type:

float

computation_memory(computation: FactorComputationNode | VariableComputationNode) → float

Memory footprint associated with the maxsum computation node.

Notes

Two formulations of the memory footprint are possible for factors : * If the constraint is given by a function (intentional), the factor

only needs to keep the costs sent by each variable and the footprint is the total size of these cost vectors.

  • If the constraints is given extensively the size of the hypercube of costs must also be accounted for.

Parameters:

computation (FactorComputationNode or VariableComputationNode) – A computation node for a factor or a variable in the factor-graph.

Returns:

the memory footprint of the computation.

Return type:

float

costs_for_factor(variable: Variable, factor: str, factors: List[RelationProtocol], costs: Dict) → Dict[Any, float]

Produce the message that must be sent to factor f.

The content if this message is a d -> cost table, where * d is a value from the domain * cost is the sum of the costs received from all other factors except f for this value d for the domain.

Parameters:

  • variable (Variable) – the variable sending the message

  • factor (str) – the name of the factor the message will be sent to

  • factors (list of Constraints) – the constraints this variables depends on

  • costs (dict) – the accumulated costs received by the variable from all factors

Returns:

a dict containing a cost for each value in the domain of the variable

Return type:

Dict

factor_costs_for_var(factor: RelationProtocol, variable: Variable, recv_costs, mode: str)

Computes the marginals to be send by a factor to a variable

The content of this message is a table d -> mincost where * d is a value of the domain of the variable v * mincost is the minimum value of f when the variable v take the

value d

Parameters:

  • factor (Constraint) – the factor that will send these cost to variable

  • variable (Variable) –

  • recv_costs (Dict) – a dict containing the costs received from other variables

  • mode (str) – “min” or “max”

Returns:

a dict that associates a cost to each value in the domain of variable

Return type:

Dict

select_value(variable: Variable, costs: Dict[str, Dict], mode: str) → Tuple[Any, float]

Select the value for variable with the best cost / reward (depending on mode)

Parameters:

  • variable (Variable) – the variable for which we need to select a value

  • costs (Dict) – a dict { factorname : { value : costs}} representing the cost messages received from factors

  • mode (str) – min or max

Returns:

a Tuple containing the selected value and the corresponding cost for this computation.

Return type:

Tuple