pydcop.algorithms.dba

DBA : Distributed Breakout Algorithm

The Distributed Breakout algorithm [YH96] is a local-search algorithm, built as a a distributed version of the Breakout algorithm for CSP [Mor93]. It is meant to solve distributed constraints satisfaction problems (and not optimization problems).

See also [WZ03] on using DBA for optimization problems.

Algorithm Parameters

Our DBA implementation supports two parameters:

infinity: the value used as ‘infinity’, returned as the cost of a violated constraint (it must map the value used in your dcop definition). Defaults to 10 000
max_distance : an upper bound for the maximum distance between two agents in the graph. Ideally you would use the graph diameter or simply the number of variables in the problem. It is used for termination detection (which in DBA only works is there is a solution to the problem). Defaults to 50

Example

pydcop -t 2 solve -a dba -p infinity:10000 max_distance:3            -d adhoc graph_coloring_csp.yaml
{
  "assignment": {
    "v1": "G",
    "v2": "R",
    "v3": "G"
  },
  "cost": 0,
  "duration": 1.9932785034179688,
  "status": "TIMEOUT"
}

Messages

class DbaOkMessage(value)

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 DbaImproveMessage(improve, current_eval, termination_counter)

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 DbaEndMessage

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

Computation

class DbaComputation(variable: Variable, constraints: Iterable[RelationProtocol], msg_sender=None, mode='min', infinity=10000, max_distance=50, comp_def=None)

DBAComputation implements DBA.

See. the following article for a description of original DBA: ‘Distributed Breakout Algorithm for Solving Distributed Constraint Satisfaction Problems’ (Makoto Yokoo, Katsutoshi Hirayama, 1996)

compute_eval_value(val, relations)

This function compute the evaluation value (the number of violated constraints) regarding the current assignment.

Parameters:

val (Any) – A value for the variable of this object. You can choose any of the definition domain, according to the context in which you use the function.
relations (list of constraints objects) – The list of constraints involving the variable of this computation, with the values of other variables set to the values sent by the neighbors

Returns:

The evaluation value for the given assignment and the list
of indices of the violated constraints for this value

property neighbors

The neighbors of this computation.

Notes

This is just a convenience shorthand to the neighbors of the node in the computation node :

my_dcop_computation.computation_def.node.neighbors

Returns:: a list containing the names of the neighbor computations.
Return type:: list of string

on_start()

Called when starting the computation.

This method is meant to be overwritten in subclasses.

class DbaComputation(variable: Variable, constraints: Iterable[RelationProtocol], msg_sender=None, mode='min', infinity=10000, max_distance=50, comp_def=None)

DBAComputation implements DBA.

See. the following article for a description of original DBA: ‘Distributed Breakout Algorithm for Solving Distributed Constraint Satisfaction Problems’ (Makoto Yokoo, Katsutoshi Hirayama, 1996)

compute_eval_value(val, relations)

This function compute the evaluation value (the number of violated constraints) regarding the current assignment.

Parameters:

val (Any) – A value for the variable of this object. You can choose any of the definition domain, according to the context in which you use the function.
relations (list of constraints objects) – The list of constraints involving the variable of this computation, with the values of other variables set to the values sent by the neighbors

Returns:

The evaluation value for the given assignment and the list
of indices of the violated constraints for this value

property neighbors

The neighbors of this computation.

Notes

This is just a convenience shorthand to the neighbors of the node in the computation node :

my_dcop_computation.computation_def.node.neighbors

Returns:: a list containing the names of the neighbor computations.
Return type:: list of string

on_start()

Called when starting the computation.

This method is meant to be overwritten in subclasses.

class DbaEndMessage

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 DbaImproveMessage(improve, current_eval, termination_counter)

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 DbaOkMessage(value)

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

communication_load(src: VariableComputationNode, target: str) → float

Return the communication load between two variables.

Notes

The main messages in DBA are the ‘ok?’ and ‘improve’ messages, which at most contains a value and a possible improvement. The size of the message does not depends on the source nor target variable, nor on their respective domains.

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 sent from the src variable to the target variable.

Return type:

float

computation_memory(computation: VariableComputationNode) → float

Return the memory footprint of a DBA computation.

Notes

With DBA, a computation must only remember the current value for each of it’s neighbors.

Parameters:: computation (VariableComputationNode) – a computation in the hyper-graph computation graph
Returns:: the memory footprint of the computation.
Return type:: float