AsymDPOP: Complete Inference for Asymmetric Distributed Constraint Optimization Problems

1 Introduction

Distributed constraint optimization problems (DCOPs) [Modi et al., 2005; Fioretto et al., 2018] are a fundamental framework in multi-agent systems where agents coordinate their decisions to optimize a global objective. DCOPs have been adopted to model many real world problems including radio frequency allocation [Monteiro et al., 2012], smart grid [Fioretto et al., 2017] and distributed scheduling [Maheswaran et al., 2004b; Li et al., 2016].

Most of complete algorithms for DCOPs employ either distributed search [Hirayama and Yokoo, 1997; Modi et al., 2005; Gershman et al., 2009; Yeoh et al., 2010] or inference [Petcu and Faltings, 2005b; Vinyals et al., 2011] to optimally solve DCOPs. However, since DCOPs are NP-hard, complete algorithms cannot scale up due to exponential overheads. Thus, incomplete algorithms [Maheswaran et al., 2004a; Zhang et al., 2005; Okamoto et al., 2016; Rogers et al., 2011; Zivan and Peled, 2012; Chen et al., 2018; Ottens et al., 2017;

∗Corresponding Author

Fioretto et al., 2016] are proposed to trade optimality for smaller computational efforts.

Unfortunately, DCOPs fail to capture the ubiquitous asymmetric structure [Burke et al., 2007; Maheswaran et al., 2004b; Ramchurn et al., 2011] since each constrained agent shares the same payoffs. PEAV [Maheswaran et al., 2004b] attempts to capture the asymmetric costs by introducing mirror variables and the consistency is enforced by hard constraints. However, PEAV suffers from scalability problems since the number of variables significantly increases. Moreover, many classical DCOP algorithms perform poorly when applied to the formulation due to the presence of hard constraints [Grinshpoun et al., 2013]. On the other side, ADCOPs [Grinshpoun et al., 2013] are another framework that captures asymmetry by explicitly defining the exact payoff for each participant of a constraint without introducing any variables, which has been intensively investigated in recent years.

Solving ADCOPs involves evaluating and aggregating the payoff for each constrained agent, which is challenging in asymmetric settings due to a privacy concern. SyncABB and ATWB [Grinshpoun et al., 2013] are asymmetric adaption of SyncBB [Hirayama and Yokoo, 1997] and AFB [Gershman et al., 2009], using an one-phase strategy to aggregate the individual costs. That is, the algorithms systematically check each side of a constraint before reaching a complete assignment. Besides, AsymPT-FB [Litov and Meisels, 2017] is the first tree-based algorithm for ADCOPs, which uses forward bounding to compute lower bounds and back bounding to achieve one-phase check. Recently, PT-ISABB [Deng et al., 2019] was proposed to improve the tree-based search by implementing a non-local elimination version of ADPOP [Petcu and Faltings, 2005a] to provide much tighter lower bounds. However, since it relies on an exhaustive search to guarantee the optimality, the algorithm still suffers from exponential communication overheads. On the other hand, although complete inference algorithms (e.g., DPOP [Petcu and Faltings, 2005b]) only require a linear number of messages to solve DCOPs, they cannot be directly applied to ADCOPs without PEAV due to their requirement for complete knowledge of each constraint to facilitate variable elimination. Accordingly, the parents have to transfer their private cost functions to their children, which leaks at least a half of privacy.

In this paper, we adapt DPOP for solving ADCOPs for the first time by deferring the eliminations of variables. Specifically, we contribute to the state-of-the-art in the following aspects.

• We propose AsymDPOP, the first complete inferencebased algorithm to solve ADCOPs, by generalizing nonlocal elimination [Deng et al., 2019]. That is, instead of eliminating variables at their parents, we postpone the eliminations until their highest neighbors in the pseudo tree. In other words, an agent in our algorithm may be responsible for eliminating several variables.
• We theoretically analyze the complexity of our algorithm where the space complexity of an agent is not only exponential in the number of its separators but also the number of its non-eliminated descendants.
• We scale up our algorithm by introducing a table-set propagation scheme to reduce the memory consumption and a mini-batch scheme to reduce the number of operations when performing eliminations. Our empirical evaluation indicates that our proposed algorithm significantly outperforms the state-of-the-art, as well as the vanilla DPOP with PEAV formulation.

2 Backgrounds

In this section we introduce the preliminaries including DCOPs, ADCOPs, pseudo tree, DPOP and non-local elimination.

2.1 Distributed Constraint Optimization Problems

A distributed constraint optimization problem [Modi et al., 2005] is defined by a tuple 〈A, X, D, F 〉 where

• A = {a1, . . . , an} is the set of agents
• X = {x1, . . . , xm} is the set of variables
• D = {D1, . . . ,Dm} is the set of domains. Variable xi takes values fromDi
• F = {f1, . . . , fq} is the set of constraint functions. Each function fi : Di1 × · · · ×Dik → R≥0 specifies the cost assigned to each combination of xi1, . . . , xik.

For the sake of simplicity, we assume that each agent controls a variable (and thus the term "agent" and "variable" could be used interchangeably) and all constraint functions are binary (i.e., fij : Di × Dj → R≥0). A solution to a DCOP is an assignment to all the variables such that the total cost is minimized. That is,

2.2 Asymmetric Distributed Constraint Optimization Problems

While DCOPs assume an equal payoff for each participant of each constraint, asymmetric distributed constraint optimization problems (ADCOPs) [Grinshpoun et al., 2013] explicitly define the exact payoff for each constrained agent. In other words, a constraint function fi : Di1×· · ·×Dik → Rk≥0 in an ADCOP specifies a cost vector for each possible combination of involved variables. And the goal is to find a solution which minimizes the aggregated cost. An ADCOP can be visualized by a constraint graph where the vertexes denote variables and the edges denote constraints. Fig. 1 presents an ADCOP with two variables and a constraint. Besides, for the constraint between xi and xj , we denote the private function for xi and xj as fij and fji, respectively.

2.3 Pseudo Tree

A pseudo tree [Freuder and Quinn, 1985] is an ordered arrangement to a constraint graph in which different branches are independent. A pseudo tree can be generated by a depthfirst traverse to a constraint graph, categorizing constraints into tree edges and pseudo edges (i.e., non-tree edges). The neighbors of an agent ai are therefore categorized into its parent P(ai), pseudo parents PP(ai), children C(ai) and pseudo children PC(ai) according to their positions in the pseudo tree and the types of edges they connect through. We also denote its parent and pseudo parents as AP(ai) = P(ai) ∪ PP(ai), and its descendants as Desc(ai). Besides, we denote its separators, i.e., the set of ancestors which are constrained with ai and its descendants, as Sep(ai) [Petcu and Faltings, 2006]. Finally, we denote ai's interface descendants, the set of descendants which are constrained with Sep(ai), as ID(ai). Fig. 2 presents a pseudo tree in which the dotted edge is a pseudo edge.

2.4 DPOP and Non-local Elimination

DPOP [Petcu and Faltings, 2005b] is an inference-based complete algorithm for DCOPs based on bucket elimination [Dechter, 1999]. Given a pseudo tree, it performs a bottomup utility propagation phase to eliminate variables and a value propagation phase to assign the optimal assignment for each variable. More specifically, in the utility propagation phase, an agent ai eliminates its variables from the joint utility table by computing the optimal utility for each possible assignment to Sep(ai) after receiving the utility tables from its children, and sends the projected utility table to its parent. In the value propagation phase, ai computes the optimal assignments for its variables by considering the assignments received from its

Algorithm 1: GNLE for ai

When Initialization: 1 utili ← ⊗ aj ∈AP (ai)fij 2 if ai is a leaf then 3 send UTIL(utili) to P(ai) When received UTIL(utilc) from ac ∈ C(ai): 4 utilc i ← utilc 5 foreach aj ∈ (PC(ai) ∩ Desc(ac)) ∪ {ac} do 6 utilc i ← utilc i ⊗ fij 7 utili ← utili ⊗ min EV (ai,ac)utilc i 8 if ai has received all UTIL from C(ai) then 9 if ai is the root then 10 start Value Propagation phase 11 else 12 send UTIL(utili) to P(ai)

parent, and propagates the joint assignment to its children. Although DPOP only requires a linear number of messages to solve a DCOP, its memory consumption is exponential in the induced width. Thus, several tradeoffs including ADPOP [Petcu and Faltings, 2005a], MB-DPOP [Petcu and Faltings, 2007] and ODPOP [Petcu and Faltings, 2006] have been proposed to improve its scalability.

However, DPOP cannot be directly applied to asymmetric settings as it requires the total knowledge of each constraint to perform optimal elimination locally. PT-ISABB [Deng et al., 2019] applies (A)DPOP into solving ADCOPs by performing variable elimination only to a subset of constraints to build look-up tables for lower bounds, and uses a tree-based search to guarantee the optimality. The algorithm further reinforces the bounds by a non-local elimination scheme. That is, instead of performing elimination locally, the elimination of a variable is postponed to its parent to include the private function enforced in the parent's side and increase the integrity of the utility table.

3 Asymmetric DPOP

The existing complete algorithms for ADCOPs use complete search to exhaust the search space, which makes them unsuitable for large scale applications. In fact, as shown in our experimental results, these search-based algorithms can only solve the problems with the agent number less than 20. Hence, in this section, we propose a complete, privacyprotecting, and scalable inference-based algorithm for ADCOPs built upon generalized non-local elimination, called AsymDPOP. An execution example can be found in the appendix (https://arxiv.org/abs/1905.11828).

3.1 Utility Propagation Phase

In DPOP, a variable could be eliminated locally without loss of completeness after receiving all the utility messages from its children since all functions that involve the variable have been aggregated. However, the conclusion does not hold for ADCOPs. Taking Fig. 2 as an example, x4 cannot be eliminated locally since the private functions f14 and f24 are not given. Thus, the local elimination to x4 w.r.t. f41 and f42 would lead to overestimate bias and offer no guarantee on the completeness. A na¨ıve solution would be that x1 and x2

transfer their private functions to their children, which would lead to an unacceptable privacy loss.

Inspired by non-local elimination, we consider an alternative privacy-protecting approach to aggregate constraint functions. That is, instead of deferring to its parent, we postpone the elimination of a variable to its highest (pseudo) parent. In this way, all the functions involving the variables have been aggregated and the variable can be eliminated from the utility table optimally. Note that the utility table is a summation of the utility tables from children and local constraints. As a result, although the utility table which contains the variable's private functions is propagated to its ancestors without elimination, the ancestors can hardly infer the exact payoffs in these private functions. We refer the bottom-up utility propagation phase as generalized non-local elimination (GNLE).

Before diving into the details of GNLE, let's first consider the following definitions.

Definition 1 (dims). The dims(·) is a function which returns the set of dimensions of a utility table.

Definition 2 (Slice). Let S be a set of key-value pairs. S[K] is a slice of S over K such that

Definition 3 (Join [Vinyals et al., 2011]). Let U,U ′ be two utility tables and DU = ×xi∈dims(U)Di,DU ′ = ×xi∈dims(U ′ )Di be their joint domain spaces. U ⊗U ′ is the join of U and U ′ over DU⊗U ′ = ×xi∈dims(U)∪dims(U ′ )Di such that

Algorithm 1 presents the sketch of GNLE. The algorithm begins with leaf agents sending their utility tables to their parents via UTIL messages (line 2-3). When an agent ai receives a UTIL message from a child ac, it joins its private functions w.r.t. its (pseudo) children in branch ac (line 5-6), and eliminates all the belonging variables whose highest (pseudo) parents are ai from the utility table (line 7). Here, EV (ai, ac) is given by

Then ai joins the eliminated utility table with its running utility table utili. It is worth mentioning that computing the set of elimination variables EV (ai, ac) does not require agents to exchange their relative positions in a pseudo tree. Specifically, each variable is associated with a counter which is initially set to the number of its parent and pseudo parents. When its (pseudo) parent receives the UTIL message containing it, the counter decreases. And the variable is added to the set of elimination variables as soon as its counter equals zero.

After receiving all the UTIL messages from its children, ai propagates the utility table utili to its parent if it is not the root (line 12). Otherwise, the value propagation phase starts (line 10).

3.2 Value Propagation Phase

In contrary to the one in vanilla DPOP which determines the optimal assignment locally for each variable, the value assignment phase in AsymDPOP should be specialized to accommodate the non-local elimination. Specifically, since a Algorithm 2: Value Propagation for ai variable is eliminated at its highest (pseudo) parent, the parent is responsible for selecting the optimal assignment for that variable. Thus, the value messages in our algorithm would contain not only the assignments for ancestors, but also assignments for descendants. Algorithm 2 presents the sketch of value propagation phase.

The phase is initiated by the root agent selecting the optimal assignment (line 14). Given the determined assignments either from its parent (line 16) or computed locally (line 15), agent ai selects the optimal assignments for the eliminated variables in each branch ac ∈ C(ai) by a joint optimization over them (line 17-20), and propagates the assignments together with the determined assignments to ac (line 21-22). The algorithm terminates when each leaf agent receives a VALUE message.

3.3 Complexity Analysis

Theorem 1. The size of a UTIL message produced by an agent is exponential in the number of its separator and its interface descendants.

Proof. We prove the theorem by showing a UTIL message produced by agent ai contains the dimensions of Sep(ai) and ID(ai) ∪ {ai}. The UTIL message must contain the dimensions of ID(ai) ∪ {ai} since ai is not the highest (pseudo) parent of aj, ∀aj ∈ ID(ai) ∪ {ai}. On the other hand, according to the definition to ID(ai), the UTIL message cannot contain the dimensions of Desc(ai)\ID(ai) since for each aj ∈ Desc(ai)\ID(ai) it must exist an agent ak ∈ Desc(ai) ∪ {ai} such that ak is the highest (pseudo) parent of aj and thus the variable is eliminated at ak (line 7). Finally, the UTIL message contains Sep(ai) according to [Petcu and Faltings, 2005b] (Theorem 1). Thus, the size of the UTIL message is exponential in |Sep(ai)| + |ID(ai)| + 1 and the theorem is concluded.

4 Tradeoffs

As shown in Section 3.3, AsymDPOP suffers serious scalability problems in both memory and computation. In this section, we propose two tradeoffs which make AsymDPOP a practical algorithm.

4.1 Table-Set Propagation Scheme: A Tradeoff between Memory and Privacy

The utility propagation phase of AsymDPOP could be problematic due to the unacceptable memory consumption when the pseudo tree is poor. Consider the pseudo tree shown in Fig. 3. Since every agent is constrained with the root agent, according to the GNLE all the variables can only be eliminated at the root agent, which incurs a memory consumption of O(dn ) due to the join operation in each agent. Here, d = maxi |Di|. Besides, a large utility table would also incur unacceptable computation overheads due to the join operations and the elimination operation (line 5-7).

We notice that utility tables are divisible before performing eliminations. Thus, instead of propagating a joint and highdimension utility table to a parent agent, we propagate a set of small utility tables. In other words, we wish to reduce the unnecessary join operations (i.e., line 1 and line 7 in the case of EV (ai, ac) = ∅) which could cause a dimension increase during the utility propagation phase. On the other side, completely discarding join operations would incur privacy leakages. For example, if an chooses to propagate both fn,n-1 and fn1 without performing the join operation to an-1, then an-1 would know the private functions of an directly. Thus, we propose to compromise the memory consumption and the privacy by a parameter kp controlling the the maximal number of dimensions of each local utility table. We refer the tradeoff as a table-set propagation scheme (TSPS).

Specifically, when an agent sends a UTIL message to its parent, it first joins its private functions w.r.t. its parents with the received utility tables whose dimensions contain the dimensions of these private functions. Notice that the first step does not incur a dimension increase, and can reduce the number of utility tables. Finally, it propagates the set of utility tables to its parent.

Consider the pseudo tree shown in Fig. 3 again. Assume that kp = 3 and then agent an would propagate the utility set utiln = {fn,n-1 ⊗ fn1} to an-1. Since there is no elimination in an-1, it is unnecessary to perform the join operation in line 7. Thus, an-1 would propagate the utility set utiln-1 = {fn-1,n-2 ⊗ fn-1,1, utiln n-1 } to an-2. It can be concluded that TSPS in the example only requires O(nd3 ) space, which is much smaller than the one required by GNLE. Formally, we have the following theorem.

Theorem 2. The size of each utility table of an agent ai in TSPS is no greater than

dmax(min(|AP(ai)|,kp), max ac∈C(ai)(|ID(ai)∩(ID(ac)∪{ac})|+|Sep(ac)|)

Proof. According to Theorem 1, the dimension of each utility table from child ac ∈ C(ai) is a subset of Sep(ac) ∪ ID(ac) ∪ {ac}. Since TSPS omits the join operation in line 7, the maximal size of received utility tables of ai is

Since the local utility is partitioned into utility tables according to kp, the maximal size of local utility tables of ai is

4.2 Mini-batch Elimination Scheme: A Tradeoff between Time and Space

TSPS could factorize a big utility table to a set of smaller utility tables, which allows us to reduce the computational efforts when performing eliminations by a decrease-and-conquer strategy. Taking Fig. 3 as an example, to perform the elimination, a1 in GNLE has no choice but to optimize a big utility table over variables x2, . . . xn (line 7), which requires O(dn ) operations. Instead, combining with TSPS (kp = 2) we could exploit the the structure of each small utility table by arranging the min operators among them to reduce computational complexity. That is, instead of performing

we perform

which can be solved recursively from xn to x2 and the overall complexity is O(nd3 ). In other words, we reduce the computational complexity by exploiting the independence among utility tables to avoid unnecessary traverses.

However, completely distributing the min operators into every variable would incur high memory consumption as a min operator could implicitly join utility tables to a big and indivisible table. Although the problem can be alleviated by carefully arranging the min operators, it is not easy to find the optimal sequence of eliminations in practice. Consider the utility tables shown as a factor graph in Fig. 4 where square nodes represent utility tables and circle nodes represent variables. And the red circles represent the variables to be eliminated. Obviously, no matter how to arrange the elimination sequence, a 3-ary utility table must appear when eliminating x1 or x2. Instead, if we jointly optimize both x1 and x2, the maximal number of dimensions are 2.

We thus overcome the problem by introducing a parameter ke which specifies the minimal number of variables optimized in a min operator (i.e., the size of a batch), and refer the tradeoff as a mini-batch elimination scheme (MBES). Specifically, when performing an elimination operation, we first divide elimination variables into several groups whose variables share at least a common utility table. For each variable group, we divide the variables into batches whose sizes are at least ke if it is possible. For each batch, we perform optimization to the functions that are related to the batch and replace these functions with the results. The process terminates when all the variable groups are exhausted.

Note that dividing variables into disjoint variable groups in the first step is crucial since optimizing independent variables jointly is equivalent to optimizing them individually. Taking Fig. 4 for example, if we set ke = 2 and let x2, x5 be a batch, a 4-ary utility table over x1, x3, x4 and x6 still appear even if x2 and x5 is jointly optimized.

5 Experimental Results

We empirically evaluate the performances of AsymDPOP and state-of-the-art complete algorithms for ADCOPs including PT-ISABB, AsymPT-FB, SyncABB, ATWB and the vanilla DPOP with PEAV formulation (PEAV DPOP) in terms of the number of basic operations, network load and privacy leakage. For inference-based algorithms, we consider the maximal number of dimensions during the utility propagation phase as an additional metric. Specifically, we use NCLOs [Netzer et al., 2012] to measure the hardware-independent runtime in which the logic operations in inference-based algorithms are accesses to the utility tables while the ones in search-based algorithms are constraint checks. For the network load, we measure the size of information during an execution. Finally, we use entropy [Brito et al., 2009] to quantify the privacy loss [Litov and Meisels, 2017; Grinshpoun et al., 2013]. For each experiment, we generate 50 random instances and report the medians as the results.

In our first experiment, we consider the ADCOPs with the domain size of 3, the density of 0.25 and the agent number varying from 8 to 24. Fig. 5 presents the experimental results under different agent numbers. It can be concluded that compared to the search-based solvers, our AsymDPOP algorithms exhibit great superiorities in terms of network load. That is due to the fact that search-based algorithms explicitly exhaust the search space by message-passing, which is quite expensive especially when the agent number is large. In contrast, our proposed algorithms incur few communication overheads since they follow an inference protocol and only require a linear number of messages. On the other hand, although PEAV DPOP also uses the inference protocol, it still suffers from a severe scalability problem and can only solve the problems with the agent number less than 12. The phenomenon is due to the mirror variables introduced by PEAV formulation, which significantly increases the complexity. More specifically, a UTIL message in PEAV DPOP contains the dimensions of mirror variables, which significantly increases the memory consumption.

Fig. 6 presents the performance comparison under different densities. Specifically, we consider the ADCOPs with the agent number of 8, the domain size of 8 and the density varying from 0.25 to 1. It can be concluded from Fig. 6(a) that AsymDPOP with TSPS (i.e., kp < w∗ where w∗ is the induced width) incurs significantly less communication overheads when solving dense problems, which demonstrates the merit of avoiding unnecessary join operations. Besides, it is interesting to find that compared to the one of AsymDPOP without TSPS (i.e., kp = w∗ ), the network load of AsymDPOP(kp < w∗ , ·) increases much slowly. That is due to the fact that as the density increases, eliminations are more likely to happen at the top of a pseudo tree. On the other hand, since unnecessary join operations are avoided in TSPS, eliminations are the major source of the dimension increase. As a result, agents propagate low dimension utility tables in most of the time. For NCLOs, search-based algorithms like AsymPT-FB and PT-ISABB outperform AsymDPOP algorithms when solving dense problems due to their effective pruning.

To demonstrate the effects of different batch sizes, we benchmark MBES with different ke when combining with TSPS with different kp on the configuration used in the first experiment. Specifically, we measure the maximal number of dimensions generated in the utility propagation phase, including the intermediate results of MBES. Fig. 7 presents the experimental results. It can be seen that AsymDPOP with a small batch size significantly reduces NCLOs but produces larger intermediate results, which indicates the necessity of the tradeoff. Besides, the performance of MBES significantly degenerates when combining with TSPS with a larger kp. That is because the utility tables contain more dimensions in the scenario, and a utility table would be traversed more frequently when performing eliminations.

In the last experiment, we consider the privacy loss of different algorithms when solving asymmetric MaxDCSPs with different tightness. In particular, we consider the asymmetric MaxDCSPs with 10 agents, the domain size of 10, the density of 0.4 and the tightness varying from 0.1 to 0.8. Fig. 8 presents the results. It can be concluded from the figure that as the tightness grows, the search-based algorithms leak more privacy while the inference-based algorithms leaks less privacy. That is due to the fact that search-based algorithms rely on a direct disclosure mechanism to aggregate the private costs. Thus, search-based algorithms would leak more privacy when solving the problems with high tightness as they need to traverse more proportions of the search space. In contrast, inference-based algorithms accumulate utility through the pseudo tree, and an agent ai could infer the private costs of its (pseudo) child ac when the utility table involving both xi and xc is a binary table which is not a result of eliminations or contains zero entries. Thus, AsymDPOP(kp = 2, ·) leaks almost a half of privacy. On the other hand, since the number of prohibit combinations grows as the tightness increases, AsymDPOP(kp ≥ 3, ·) incurs much lower privacy loss when solving high tightness problems.

6 Conclusion

In this paper we present AsymDPOP, the first complete inference algorithm for ADCOPs. The algorithm incorporates three ingredients: generalized non-local elimination which facilitates the aggregation of utility in an asymmetric environment, table-set propagation scheme which reduces the memory consumption and mini-batch elimination scheme which reduces the operations in the utility propagation phase. We theoretically show its complexity and our empirical evaluation demonstrates its superiorities over the state-of-the-art, as well as the vanilla DPOP with PEAV formulation.

Acknowledgements

We would like to thank the anonymous reviewers for their valuable comments and helpful suggestions. This work is supported by the Chongqing Research Program of Basic Research and Frontier Technology under Grant No.:cstc2017jcyjAX0030, Fundamental Research Funds for the Central Universities under Grant No.: 2018CDXYJSJ0026, National Natural Science Foundation of China under Grant No.: 51608070 and the Graduate Research and Innovation Foundation of Chongqing, China under Grant No.: CYS17023