Summary of "Distributed Constraint Optimization with Structured Resource Constraints"

Read a very interesting paper today, here it is in a summary:


Presents a method for solving distributed constraint optimization problems applied to power networks using an extended DPOP. Represents the problem as a network of nodes which are either power sources or sinks (i.e. transformers which consume some power and pass the rest on to there various connected nodes). An edge between a node represents a transmission line and contains a maximum power constrain. The kirchhoff law is also applied to the entire network such that each transmission line must carry enough power for its directly connected sinks and all the sinks below it in the tree.

A number of feeder trees is used to present a network of this nature such that each feeder tree contains a power source as its root and consists of an acyclic tree with sinks at various levels. The idea is that it attempts to find a value for each agent such that sinks and loads are satisfied. It priovides two methods, one using resource quantification which descretizes resources (However this doesn't scale very well). The other uses resource abstraction which is a more general solution and scales very well. This solution uses partial feeder trees.

Two techniques for speeding the algorithm up are presented: inconsistent and dominated pruning. Inconsistent pruning uses the fact that the power at a parent should be greater then the power wanted by a child node. Therefore if a sink wants more power then its parent has this is inconsistent and thererfore this branch of the solution tree can be pruned.

Dominated pruning happens when more then one complete feeder tree exists that both have the same root and feed the same set of nodes. Thus the higher costing tree can be pruned. A set of results is presented which is benchmarked using the power network configuration made publicly available in [8]