Distributed constraint optimization

A DCOP is a problem in which a group of agents must distributedly choose values for a set of variables such that the cost of a set of constraints over the variables is minimized.

Distributed Constraint Satisfaction is a framework for describing a problem in terms of constraints that are known and enforced by distinct participants (agents).

The constraints are described on some variables with predefined domains, and have to be assigned to the same values by the different agents.

Problems defined with this framework can be solved by any of the algorithms that are designed for it.

[citation needed] The main ingredients of a DCOP problem are agents and variables.

Importantly, each variable is owned by an agent; this is what makes the problem distributed.

, where: The objective of a DCOP is to have each agent assign values to its associated variables in order to either minimize or maximize

This can be thought of as a function mapping variables in the DCOP to their current values:

Note that a context is essentially a partial solution and need not contain values for every variable in the problem; therefore,

An optimal solution is a full assignment in which the objective function

is optimized (i.e., maximized or minimized, depending on the type of problem).

Various problems from different domains can be presented as DCOPs.

, such that the number of adjacent vertices with the same color is minimized.

As a DCOP, there is one agent per vertex that is assigned to decide the associated color.

Each agent has a single variable whose associated domain is of cardinality

, there is a constraint of cost 1 if both of the associated variables are assigned the same color:

The distributed multiple- variant of the knapsack problem is as follows: given a set of items of varying volume and a set of knapsacks of varying capacity, assign each item to a knapsack such that the amount of overflow is minimized.

represents the total weight assigned by context

The item allocation problem can be formulated as a DCOP as follows.

[2] DCOP was applied to other problems, such as: DCOP algorithms can be classified in several ways:[3] ADOPT, for example, uses best-first search, asynchronous synchronization, point-to-point communication between neighboring agents in the constraint graph and a constraint tree as main communication topology.

Synchronous Branch and Bound Iterative Distributed Breakout DCOPolis (GNU LGPL)

The vector of costs is of length k if each variable belongs to a different agent; if two or more variables belong to the same agent, then the vector of costs is shorter - there is a single cost for each involved agent, not for each variable.

A simple way for solving an ADCOP is to replace each constraint

However, this solution requires the agents to reveal their cost functions.

[14][15][16] Another approach is called Private Events as Variables (PEAV).

The disadvantage of this method is that the number of variables and constraints is much larger than the original, which leads to a higher run-time.

A third approach is to adapt existing algorithms, developed for DCOPs, to the ADCOP framework.

[13] The structure of an ADCOP problem is similar to the game-theoretic concept of a simultaneous game.

However, there is a fundamental difference:[13] There are some intermediate models in which the agents are partially-cooperative: they are willing to decrease their utility to help the global goal, but only if their own cost is not too high.

Therefore, they are willing to help others or do some other time-consuming tasks that help the firm, as long as it is not too burdensome on them.