DeQED: An Efficient Divide-and-Coordinate Algorithm for DCOP

1 Introduction

In many applications of distributed problem solving, the agents may want to optimize a global objective while preserving their privacy and security. This problem can be formalized as the Distributed Constraint Optimization Problem (DCOP). To solve DCOP, several complete algorithms have been presented in the literature [Modi et al., 2005; Petcu and Faltings, 2005], but one recent trend may be incomplete algorithms [Farinelli et al., 2008; Kiekintveld et al., 2010; Vinyals et al., 2010a; 2010b] due to the need to find highquality solutions quickly for large-scale problem instances.

This paper presents a new DCOP algorithm called DeQED (Decomposition with Quadratic Encoding to Decentralize). DeQED is based on the Divide-and-Coordinate (DaC) framework, where the agents repeatedly solve their updated local sub-problems (the divide stage) and exchange coordination information that causes them to update their local subproblems (the coordinate stage). Unlike other DaC-based DCOP algorithms [Vinyals et al., 2010a; 2010b], DeQED does not essentially increase the complexity of local subproblems and allows agents to avoid exchanging (primal) variable values in the coordinate stage.

∗Current Affiliation: National Institute of Informatics,

2-1-2 Hitotsubashi, Chiyoda-ku, Tokyo, 101-8430, Japan

† JST, ERATO, Kawarabayashi Large Graph Project, Japan

Through comparison with MaxSum [Farinelli et al., 2008], DALO [Kiekintveld et al., 2010], and EU-DaC [Vinyals et al., 2010b], we demonstrate that DeQED works very well both in terms of solution quality and efficiency.

The remainder of this paper is organized as follows. We first introduce DCOP and the DaC framework in Section 2, followed by the details of DeQED in Section 3. We experimentally compare DeQED with other incomplete DCOP algorithms in Section 4 and conclude this work in Section 5.

2 DCOP and DaC framework

COP is defined by a set X of variables, where each variable xi has a finite domain Di from which it takes its value, and a set F of binary cost functions, where each function fi,j : Di ×Dj → ℜ+ returns a non-negative cost value for each binary relation between variable xi's domain and variable xj's domain.

DCOP is the COP where variables are controlled by a set A of agents. Each variable belongs to some agent who controls it. We denote the fact that variable xi belongs to agent a by belong(xi) = a. The goal of COP and DCOP is to find a value assignment to X that minimizes the total sum of the values of cost functions.

In DCOP, the cost functions are divided into a set Finter of inter-agent cost functions and a set Fintra of intra-agent cost functions. Formally, we define Finter ≡ {fi,j | belong(xi) ̸= belong(xj)} and Fintra ≡ {fi,j | belong(xi) = belong(xj)}.

An agent in DCOP may have multiple variables in its control. These multiple variables of an agent can be divided into two sets. One is the set of variables involved in interagent cost functions, which we call interface variables. A set of interface variables of agent a is defined by Xa inf ≡ {xi | belong(xi) = a, ∃xj(fi,j ∈ Finter ) ∨ (fj,i ∈ Finter )}. The other is the set of variables that is not involved in any inter-agent cost functions, which we call hidden variables. A set of hidden variables of agent a is defined by Xa hid ≡ {xi | belong(xi) = a, xi ̸∈ Xa inf }.

DaC (Divide-and-Coordinate) is the framework for solving DCOP, where the agents repeatedly solve their updated local sub-problems (the divide stage) and exchange coordination information that causes them to update their local subproblems (the coordinate stage). The work in [Vinyals et al., 2010a; 2010b] has instantiated this framework as follows. The problem is divided in such a way that the resulting sub-problems share some variables, each of which yields an inter-agent equality constraint among its copies. The value assignments on these copies (interface variables) may be in disagreement with each other when the agents solve their subproblems independently. Therefore, the agents iterate the following two stages to reach the state where the assignments on every variable's copies are in agreement.

divide stage: Each agent updates its own sub-problem with information received from its neighbors and solves this updated sub-problem.

coordinate stage: Each agent sends information about disagreement on variables to its neighbors.

Both DaCSA [Vinyals et al., 2010a] and EU-DaC [Vinyals et al., 2010b] are DaC-based algorithms. Agents in DaCSA control Lagrange multipliers, each of which is defined for any shared variable, while agents in EU-DaC control coordination parameters, so that value assignments on every variable's copies are in agreement. It must be noted that, even when solving a DCOP instance with one variable per agent, each agent in DaCSA and EU-DaC has a tree-structured local sub-problem.

3 DeQED

As with DaCSA, DeQED exploits the Lagrangian decomposition technique, but the difference between DeQED and DaCSA is the way of encoding of the entire problem. In DeQED, we use quadratic encoding, in which an inter-agent cost function is encoded into the quadratic programming problem. Let us start this section by presenting the details of the quadratic encoding.

3.1 Quadratic encoding

Let us assume that every variable has the same domain, say D, without loss of generality. For cost function fi,j ∈ F between variable xi and variable xj , we introduce the following |D| × |D| cost matrix:

whose element ci,j m,n represents the cost when we assign variable xi the mth value of domain and variable xj the nth value of domain. Furthermore, for variables xi and xj, we introduce new variables xi and xj respectively, whose domains are the whole set of |D|-dimensional unit column vectors. Namely, we have xi ∈ {e1, e2, . . . , e|D|} and xj ∈ {e1, e2, . . . , e|D|}, where e1 is (1, 0, 0, . . . , 0)T, e2 is (0, 1, 0, . . . , 0)T, and so on. Superscript T means the transpose of a vector.

Given this representation, the value of cost function fi,j can be computed by (xi)T · Fi,j · xj. For example, when xi takes the mth value and xj takes the nth value, the cost is computed by (em)T ·Fi,j ·en, resulting in the (m, n)-element of Fi,j .

Therefore, DCOP can be formulated as

DCOP :

Since the intra-agent cost functions are partitioned among the agents, we can put the intra-agent cost functions on agent a together to produce one black-box function ϕa that returns, given an assignment to the variables, the sum of the values of a's intra-agent cost functions. With this black-box function, we can reformulate DCOP as follows:

We introduce two auxiliary variables αi,j i andαi,j j for each inter-agent cost function fi,j. These auxiliary variables are supposed to be the copies of interface variables xi and xj in terms of fi,j, respectively. Hence, we have an equivalent description of the above DCOP as follows:

DCOP ′ :

where α and x are decision variables. Due to space limitations, we omit the last two lines of the above formulation because they just describe the domain of these decision variables.

3.2 Lagrangian Decomposition

We decompose this problem into the sub-problems over the agents. First, we relax a set of copy constraints (1) to produce the Lagrangian relaxation problem:

where both µi,j i andµi,j j are |D|-dimensional real-valued column vectors and called Lagrange multiplier vectors. For any fixed values for µ, the optimal value of L, denoted by L(µ), provides a lower bound on the optimal value of DCOP ′ .

Then, we decompose the objective function of L into the terms on the individual agents and the terms on auxiliary variables. As a result, we get the sub-problem on the agents:

Lagn : Lagn (µ)

where P a ≡ {(xi, xj) | fi,j ∈ Finter , belong(xi) = a} and N a ≡ {(xi, xj) | fi,j ∈ Finter , belong(xj) = a}. We also get the sub-problem on auxiliary variables:

Note that, except for µ, these sub-problems do not share any decision variables; even the sub-problems on agents do not share their decision variables.

Given fixed values for µ, the sub-problem giving La (µ) of each agent a can be viewed as the Weighted Constraint Satisfaction Problem (WCSP). For example, the term of (µi,j i )Txi is a unary soft constraint on variable xi whose weights for domain values are µi,j i . Furthermore, ϕa (X) is actually a set of binary soft constraints. On the other hand, it is trivial to solve the sub-problem giving Laux i,j (µ) of each inter-agent cost function fi,j because we just select an optimal pair of values for the cost matrix that is modified with µ.

To summarize, we get the following Lagrangian decomposition:

3.3 Lagrangian Dual

The goal of the Lagrangian dual problem is to maximize the lower bound that is obtained by solving the Lagrangian relaxation problem by controlling values of µ. With the above decomposition, it is formally defined by

Clearly, the value of the objective function of D provides a lower bound on the optimal value of DCOP ′ .

DeQED solves this decomposed Lagrangian dual problem by searching for the values of µ that give the highest lower bound on the optimal value of DCOP ′ .

3.4 ProblemDistribution

We need to clarify which agent should compute which part of (2). Regarding the primal phase, where we solve the minimization problem over x and α with specific values on µ, we propose that

• La (µ) should be computed by agent a since it includes only agent a's variables;
• Laux i,j (µ) should be computed by either of the agents who control variables xi or xj since it represents interagent cost function fi,j between these agents.

On the other hand, regarding the dual phase, where we solve the maximization problem over µ with specific values on x and α, we propose that

• since Lagrange multiplier vectors µi,j i and µi,j j are related to inter-agent cost function fi,j, both vectors should be controlled by the agents having variables xi and xj, respectively.

Let us present an example. In Figure 1 (a), nodes are variables, edges are binary cost functions, and boxes are agents. The Lagrangian dual problem of this example consists of the following:

• X = {x1, x2, . . . , x6}, A = {1, 2, 3},
• Finter = {f1,4, f2,5, f4,6}, Fintra = {f1,2, f3,4, f5,6},
• P 1 = {(x1, x4), (x2, x5)}, N 1 = {},
• P 2 = {(x4, x6)}, N 2 = {(x1, x4)},
• P 3 = {}, N 3 = {(x2, x5), (x4, x6)},
• ϕ1 (X) returns the objective of COP : {(x1, x2), (f1,2)},
• ϕ2 (X) returns the objective of COP : {(x3, x4), (f3,4)},
• ϕ3 (X) returns the objective of COP : {(x5, x6), (f5,6)},
• L1 (µ) = min {ϕ1 (X) + (µ1,4 1 )Tx1 + (µ2,5 2 )Tx2},
• L2 (µ) = min {ϕ2 (X) + (µ4,6 4 )Tx4 + (µ1,4 4 )Tx4},
• L3 (µ) = min {ϕ3 (X) + (µ2,5 5 )Tx5 + (µ4,6 6 )Tx6},
• Laux 1,4 (µ) = min {(α1,4 1 )T ·F1,4 ·α1,4 4 -(µ1,4 1 )Tα1,4 1 - (µ1,4 4 )Tα1,4 4 },

• Laux 2,5 (µ) = min {(α2,5 2 )T ·F2,5 ·α2,5 5 -(µ2,5 2 )Tα2,5 2 - (µ2,5 5 )Tα2,5 5 },
• Laux 4,6 (µ) = min {(α4,6 4 )T ·F4,6 ·α4,6 6 -(µ4,6 4 )Tα4,6 4 - (µ4,6 6 )Tα4,6 6 }.

We propose to distribute these components over the agents as depicted in Figure 1 (b), where

• Agent 1 computes L1 (µ), Laux 1,4 (µ)/2, and Laux 2,5 (µ)/2 while controlling µ1,4 1 and µ2,5 2 . Note that, in computing Laux 1,4 (µ)/2 and Laux 2,5 (µ)/2, it needs µ1,4 4 and µ2,5 5 , which are controlled by the other agents.
• Agent 2 computes L2 (µ), Laux 1,4 (µ)/2, and Laux 4,6 (µ)/2 while controlling µ1,4 4 and µ4,6 4 . Note that, in computing Laux 1,4 (µ)/2 and Laux 4,6 (µ)/2, it needs µ1,4 1 and µ4,6 6 , which are controlled by the other agents.
• Agent 3 computes L3 (µ), Laux 2,5 (µ)/2, and Laux 4,6 (µ)/2 while controlling µ2,5 5 and µ4,6 6 . Note that, in computing Laux 2,5 (µ)/2 and Laux 4,6 (µ)/2, it needs µ2,5 2 and µ4,6 4 , which are controlled by the other agents.

We should emphasize that, given values of µ, La (µ) for agent a is a WCSP on variables x, and Laux i,j (µ) for inter-agent cost function fi,j is a trivial problem on auxiliary variables α. In the above, each Laux i,j (µ) is divided by two and shared between a pair of agents. This is due to making the total sum of La (µ) over the agents and Laux i,j (µ) over the inter-agent cost functions equal to the objective of (2).

3.5 Minimal Procedure

Below is the minimal procedure of DeQED, where the agents try to find values for µ that minimize the objective of (2).

• Step 1: The agents initialize their µ as (0, . . . , 0)T.
• Step 2: Every agent a sends, for each inter-agent cost function fi,j with belong(i) = a, the value of µi,j i to the agent to which xj belongs. Similarly, it sends, for each inter-agent cost function fi,j with belong(j) = a, the value of µi,j j to the agent to which xi belongs.
• Step 3: After receiving all of the latest values for µ, every agent a solves La (µ) by an exact WCSP solver and Laux i,j (µ) by evaluating all possible pairs of the values for xi and xj.
• Step 4: If CanTerminate? then the agents stop; otherwise they update µ and go back to Step 2.

We refer to one iteration from Steps 2 to 4 as a cycle.

Next, we focus on Step 4, giving the details of what conditions cause the agents to stop and how to update Lagrange multiplier vector µ in every cycle. Before doing so, however, it is worth mentioning how the agents can explicitly compute upper and lower bounds on the global optimal values of the original DCOP.

3.6 Computing Upper and Lower Bounds

DeQED can work in its minimal form. In that case, if it is successfully terminated, a final assignment for the variables is guaranteed to be globally optimal. However, if it terminates due to a time limit, agents in the minimal DeQED get only an assignment for their variables with no extra information. If the agents require a lower or upper bound on the global optimal, they need to explicitly communicate those bounds.

Remember that the value of the objective of (2) gives a lower bound on the global optimal. Thus, as with the method in [Hirayama et al., 2009], agents can compute a lower bound by explicitly collecting all of the values of La (µ) and Laux i,j (µ) over the agents at a certain cycle by using a spanning tree. Note that, by this method, agents need to exchange the objective values of sub-problems but do not need to exchange an assignment on interface variables.

On the other hand, if we allow agents to exchange an assignment on interface variables, they can compute their pieces of the global objective. By collecting those pieces using a spanning tree, agents can compute an upper bound on the global optimal.

These upper and lower bounds can be computed on-line in every cycle by overlaying a distributed data-collection protocol on the minimal DeQED. Furthermore, as we shall see later, the agents in DeQED can exploit the best bounds, BestUB and BestLB, among those computed in deciding when to terminate the procedure and how to update the µ. We refer to this extended version of DeQED as DeQEDa and to the minimal version of DeQED as DeQEDm.

It is noteworthy that the agents in DeQEDm only exchange dual variables. Namely, they do not have to exchange values of interface variables. Considering that one major motivation of DCOP is privacy and security, this property of DeQEDm should be important.

3.7 Termination

At Step 4 in the procedure, we have the following three criteria to make the agents terminate themselves.

satisfying relaxed constraints Since we have relaxed equality constraints (1) of DCOP ′ , we can ensure that if the solutions to the sub-problems at Step 3 happen to satisfy all of the relaxed constraints, then these solutions constitute an optimal solution to DCOP. To detect the fact that all of the relaxed constraints are satisfied, the agents need to take a snapshot of the system, which can be done by using a spanning tree.

achieving a quality bound When the agents compute BestUB and BestLB as in Section 3.6, they can terminate themselves if BestUB/BestLB becomes no more than a specified quality bound. The agents end with a global optimal solution if the quality bound is set to one.

exceeding a time limit Obviously, the agents terminate themselves whenever they use up the time allowed.

Clearly, DeQEDa terminates with any of these three criteria while DeQEDm does with the first or third one.

3.8 Updating Lagrange Multipliers

If none of the above criteria is met, the agents update their own µ aiming at a tighter (higher) lower bound on the optimal value of DCOP. This involves a search algorithm for the Lagrangian dual problem. We solve this problem with the sub-gradient ascent method [Bertsekas, 1999]. Here are the details of this method.

For each inter-agent cost function fi,j,

1. the agents with xi and xj compute sub-gradient Gi,j i and Gi,j j as:

which correspond to the coefficients of µi,j i and µi,j j , respectively, in the objective function of L.

1. they update µi,j i and µi,j j as

where D is a scalar parameter, called step length, which is computed differently depending on the implementations of algorithm.

This method implies that an agent increases (decreases) the value of the Lagrange multiplier if its corresponding coefficient in the objective function of L is positive (negative), hoping that L(µ), a lower bound on the optimal value of DCOP, increases in the next cycle.

To compute step length, DeQEDm follows a simple diminishing strategy where starting from a certain value of D (e.g. 10% of the possible maximum cost), we gradually reduce it by half after keeping its value for a fixed number of cycles (e.g. 10 cycles). Note that DeQEDm should require some tuning process to find a valid schedule for diminishing step length.

On the other hand, DeQEDa follows the conventional strategy, where we compute step length by

in which π is a scalar parameter that, starting from its initial value of two, is reduced by half when BestLB is not updated for a certain consecutive number of cycles (e.g. five cycles).

Although the sub-gradient ascent method is quite simple, it does not necessarily converge to an optimal solution to DCOP. Thus, both DeQEDm and DeQEDa are incomplete.

4 Experiments

We compared DeQED with DALO [Kiekintveld et al., 2010], EU-DaC [Vinyals et al., 2010b], and MaxSum [Farinelli et al., 2008] on binary constraint networks with random, regular grid, and scale-free topologies. We did not adopt DaCSA since it was outperformed by EU-DaC [Vinyals et al., 2010b].

Details on how to generate instances for each topology are as follows.

random : We created an n-node network whose density is the ratio of d, resulting in ⌊n(n - 1) ∗ d⌋ edges in total.

• regular grid : We created an n-node network arranged in a rectangular grid, where each node is connected to four neighboring nodes (except when it is located on the boundary).

scale-free : We created an n-node network based on the Barabasi-Albert (BA) model, where starting from two nodes with an edge, we added a node one-by-one while randomly connecting the added node to two existing nodes by new edges. Such two nodes are selected with probabilities that are proportional to the numbers of their connected edges. The total number of edges is 2(n - 2) + 1.

We created 20 instances for each of these three topologies. For each instance of these networks, we ascertained its connectivity. Namely, there is no disconnected sub-network in every instance.

We created a COP instance for each instance of networks, where the domain size of all variables (nodes) is three and the cost value of binary cost functions (edges) is randomly selected from {1, 2, ..., 105}. Then, following the convention in the literature, we created a DCOP instance so that one agent has exactly one variable and its related cost functions.

Our experiments were conducted on a discrete event simulator that simulates concurrent activities of multiple agents using the cycle-base mechanism, where the agents repeat the cycle of receiving messages, perform local computations, and sending messages until a termination condition is met.

To evaluate the performance of each algorithm, we measured the number of cycles, simulated runtime [Sultanik et al., 2007] and quality upper bound on this simulator. The number of cycles is one of the conventional measures to evaluate the performance of the DisCSP or DCOP algorithm, while the simulated runtime is a relatively new measure, which corresponds to the longest sequence of runtime on the agents. For each algorithm, the quality upper bound is computed by dividing the obtained global cost by BestLB that is computed by DeQEDa. Note that the obtained global cost is the one at a cutoff cycle for DeQEDm while BestUB (the best upper bound found by a cutoff cycle) for other algorithms including DeQEDa. On the quality upper bound, a figure closer to one is better.

Since all of the algorithms are incomplete, our interest is on how quickly each of these algorithms finds a better solution. Therefore, in our experiments, we observed an average quality upper bound for each algorithm when cutting off a run at a certain cycle bound, which ranges from 50 to 500 cycles in steps of 50. Furthermore, since these algorithms clearly have different computational costs in one cycle, we also observed an average quality upper bound against simulated runtime at the above cut-off cycles.

These experiments were conducted on an Intel Core-i7 2600@3.4GHz with 4 Cores, 8 threads and 8 GB memory. The main codes of DeQED and EU-DaC were written in Java and compiled with JDK 1.6.0-20 on Ubuntu 11.10 (64 bit). We downloaded DALO from the USC DCOP Repository and used the DALO-t with t = 1. On the MaxSum algorithm, we used the code in the FRODO version 2.10.5 [L´eaut´e et al., 2009] with a default setting.

The results are shown in Figure 2, where the left part denoted by (a) shows the average quality upper bound against the number of cycles and the right part denoted by (b) shows the average quality upper bound against simulated runtime.

In these figures, we omit the results of DALO and EU-DaC because their quality upper bounds were more than 1.4, even in the best case. Moreover, EU-DaC spent more than 10,000 ms of the simulated runtime to finish 500 cycles. Thus, we plot the average quality upper bounds with error bars only for MaxSum, DeQEDm and DeQEDa for readability.

Figure 2 shows that DeQED clearly outperformed MaxSum for any topology of networks. In particular, DeQED converged quite efficiently in the simulated runtime. One reason for this efficiency is that the computational cost of each agent in DeQED increases only linearly with the number of its neighbors, while that in MaxSum increases exponentially [Farinelli et al., 2008].

When comparing DeQEDm and DeQEDa, we observed that DeQEDa generally shows faster convergence than DeQEDm with respect to the number of cycles, but DeQEDm is slightly faster than DeQEDa with respect to simulated runtime. The reason behind this difference is that the agents in DeQEDa are required to collect and compute upper and lower bounds on-line, which imposes extra computation on the agents. On the other hand, the agents in DeQEDm do not have to perform such extra computation.

We should also point out that EU-DaC, another algorithm based on the DaC framework, did not perform well especially in simulated runtime. An agent in EU-DaC solves the local problem that includes the copies of variables of neighboring agents and tries to make an agreement on the assignments between their copies and originals. Thus, even for the DCOP with one variable per agent, EU-DaC has to solve much larger local problems, which clearly increases the cost of local computations. On the other hand, in DeQED, the local problem of each agent is still trivial for the DCOP with one variable per agent.

Moreover, we also compared DeQEDa and EU-DaC with respect to the tightness of their bounds as the cycle proceeds. Similar to the experiments in [Vinyals et al., 2010b], we measured bound guarantee at a certain number c of cycles for each algorithm A, which is defined by

where BestLBA(c) is the highest lower bound that algorithm A has found by the cycle of c, and BestUBA(c) is the lowest upper bound that algorithm A has found by the cycle of c. The results are shown in Figure 3, where the x-axis indicates the number of cycles and the y-axis indicates the bound guarantees averaged over 20 instances. From these results, we can say that DeQEDa can always obtain tighter bounds than EU-DaC.

5 Conclusions

We provided a new DCOP algorithm called DeQED (Decomposition with Quadratic Encoding to Decentralize). The contribution of DeQED is twofold.

First, DeQED does not essentially increase the complexity of local subproblems. The previous DaC-based algorithms, DaCSA and EU-DaC, solve the local problem that includes the copies of variables of neighboring agents, which clearly increases the cost of local computations. However, in DeQED, the local problem of each agent is trivial.

Second, it allows agents to avoid exchanging (primal) variable values in the coordinate stage. The agents in DaCSA and EU-DaC need to exchange (primal) variable values. However, the agents in DeQED can exchange only the values of Lagrange multipliers.

Furthermore, we experimentally confirmed that DeQED worked significantly better than other representative incomplete DCOP algorithms.