pydcop.distribution.gh_secp_cgdp

GH-SECP-CGDP : Greedy Heuristic for the SECP Constraint Graph Distribution Problem

In order to minimize communication load, we assign the computations for each yj to one of the agents already hosting a variable that shares a constraint with yj . This of course only holds if the algorithm supports n-ary constraints and we do not need to apply any binarization methods, which would introduce additional auxiliary variables that must be distributed on agents.

When implementing this heuristic, we use a greedy approach to select one agent among the set of valid agents for a given computation: we select the agent, with enough capacity, that is already hosting the highest number of computations that share a dependency with the computation we are placing. In case of tie, we chose the agent with the highest remaining capacity. By grouping interdependent computations, this approach favors distributions with a low communication cost.

Notice that * the communication load is not used in this distribution method * the computation footprint is required

This distribution method is designed for SECP and makes the following assumptions on the DCOP: * variables that represent an actuator are assigned to an agent, with an hosting cost of 0