Cluster and mini-cluster tree elimination are well-known solving methods for constrained optimization problems, developed for the centralized case. These methods, based on cost function combination, can be easily reformulated as synchronous algorithms to solve the distributed versions of the above mentioned problems. During solving they exchange a linear number of messages, but these messages could be of exponential size, which is their main drawback that often limits their practical application. Filtering is a general technique to decrease the size of cost function combination when using upper and lower bounds. We combine this technique with the previous algorithms, producing a signi cative decrement in message size and improving their practical memory usage. As result, the improved algorithm is able to solve larger problems, keeping under control memory consumption.
Most of constraint reasoning methods have been developed under the
implicit assumption that the constraint network is in the memory of a single
agent, which performs the solving task. This is called centralized solving. In
the last years, there is an increasing interest to solve these problems in a
distributed form, when di erent problem parts are in the memory of di erent
agents and they cannot be joined into a single one (because incompatible
formats, privacy, etc.). New solving algorithms have been developed for this
distributed model, where communication between agents is done by message
passing. As examples, we mention ABT [
In the centralized case, there are di erent forms to decompose a problem
instance [
The paper is organized as follows. In section 2, we provide a precise de nition of the problems we consider. To make a self-contained paper, we summarize some centralized solving algorithms in section 3, while the idea of function ltering appears in section 4. Moving into a distributed context, we present new solving algorithms based on these ideas in sections 5 and 6, including distributed function ltering. The distributed algorithm to build cluster trees appears in section 7, with an example to clarify these new algorithms in section 8. Finally, section 9 contains some conclusions. 2
In a centralized setting, a Constraint Optimization Problem (COP) involves a nite set of variables, each one taking a value in a nite domain. Variables are related by cost functions that specify the cost of value tuples on some variable subsets. Costs are natural numbers (including zero and 1). Formally, a nite COP is de ned by a triple (X; D; C),
X = fx1; : : : ; xng is a set of n variables; D = fD(x1); : : : ; D(xn)g is a collection of nite domains; D(xi) is the initial set of possible values for xi; C is a set of cost functions; fi 2 C on the ordered set of variables var(fi) = (xi1 ; : : : ; xir(i) ) speci es the cost of every combination of values for the variables in var(fi), that is, fi : Qiri j=i1 D(xj ) 7! N + (where N + is the set of natural numbers including 0 and 1). The arity of fi is the cardinality of the set var(fi).
The overall cost of a complete tuple (involving all variables) is the addition of all individual cost functions on that particular tuple. A solution is a complete tuple whose overall cost is not unacceptable. A solution is optimal if its overall cost is minimal.
Previous COP de nition does not make explicit the fact that there is an
upper bound in the cost of acceptable value tuples, so those value tuples
whose cost exceeds this upper bound can be safely removed. In addition,
this upper bound may change during problem resolution. To make explicit
these ideas, COP de nition is re ned to produce the so called Weighted
Constraint Satisfaction Problem (WCSP). Formally, a WCSP is de ned as
a four tuple (X; D; C; S(k)), where X and D are as in the previous de nition,
C is a set of cost functions and S(k) is a valuation structure [
This de nition can be extended to a distributed context. A Distributed Weighted Constraint Satisfaction Problem (DWCSP), is a WCSP where variables, domains and cost functions are distributed among automated agents. Formally, we de ne a variable-based (resp. cost-function-based ) DWCSP as a 6-tuple (X; D; C; S(k); A; (resp. )), where X, D, C and S(k) de ne a WCSP, A is a set of p agents and (resp. ) maps each variable (resp. cost function) to one agent. Here we assume the DWCSP model: it is a re ned version of distributed constraint optimization, where the notion of unacceptable cost is explicitly handled. In the rest of the paper, we will assume the cost-function-based de nition of DWCSP.
Next, some terminology to be used in the rest of the paper. An assignment or tuple tS with scope S is an ordered sequence of values, each corresponding to a variable of S X. The projection of tS on a subset of variables T S, written tS[T ], is formed from tS removing the values of variables that do not appear in T . This idea can be extended to cost functions: the projection of f on T var(f ), is a new cost function f [T ] formed by the tuples of f removing the values of variables that do not appear in T , removing duplicates and keeping the minimum cost of the original tuples in f . The join of two tuples tS and t0T , written tS 1 t0T , is a new tuple with scope S [ T , formed by the values appearing in tS and t0T ; it is only de ned when common variables have the same values in tS and t0T . The cost of a tuple tX (involving all variables) is f2C f (tX ), that is, the addition of the individual cost functions evaluated on tX (implicitly, it is assumed that, for each f 2 C; f (tX ) = f (tX [var(f )])). A solution is a tuple with cost lower than k. A solution is optimal if its cost is minimal.
Centralized WCSPs can be solved using tree decomposition methods. A
tree decomposition of a WCSP hX; D; C; S(k)i is a triple hT; ; i, where
T = hV; Ei is a tree, and are labeling functions which associate with
each vertex v 2 V two sets, (v) X and (v) C such that
for each cost function f 2 C, there is exactly one vertex v 2 V such
that f 2 (v); in addition, var(f ) (v);
for each variable x 2 X, the set fv 2 V jx 2
subtree of T .
(v)g induces a connected
The tree-width of hT; ; i is tw = maxv2V j (v)j. If u and v are adjacent
vertices, (u; v) 2 E, its separator is sep(u; v) = (u) \ (v) [
The Cluster-Tree Elimination algorithm (CTE) solves WCSP by sending
messages along tree decomposition edges [
Mini-Cluster-Tree Elimination (MCTE(r)) approximates CTE. If the number of variables in u is high, it may be impossible to compute m(u;v) due to memory limitations. MCTE(r) computes a lower bound by limiting to r the maximum arity of the functions sent in the messages. A MCTE(r) message, M(u;v), is a set of functions that approximate the corresponding CTE message m(u;v) (M(u;v) m(u;v)). It is computed as m(u;v) but instead of summing all functions of set B (see Figure 1), it computes a partition P = fP1; : : : ; Pqg of B such that the arity of the sum of functions in every procedure CTE(hX; D; C; S(k)i, hhV; Ei; ; i) 1 for each (u; v) 2 E s.t. all m(i;u); i 6= v have arrived do 2 B (u) [ fm(i;u) j (i; u) 2 E; i 6= vg; 3 m(u;v) (Pf2B f )[sep(u; v)]; 4 send m(u;v); Pi does not exceed r. The MCTE(r) algorithm is obtained replacing line 3 of CTE by the following lines (where the projection is done on the variables of the separator that appear in the scope of the functions in the partition class), 3:1 fP1; :::; Pqg partition(B; r); 3:2 M(u;v) f(Pf2Pi f )[sep(u; v) \ ([f2Pi var(f ))] j i : 1:::qg; 4
Filtering cost functions is a clever strategy to decrease the size of messages
sent by CTE and MCTE(r). It was introduced for the centralized case in
[
A nogood is a tuple t that cannot be extended into a complete assignment with acceptable cost. Nogoods are useless for solution generation, so they can be eliminated as soon as are detected. For summing f + g, we iterate over all the combinations (t; f (t)) 2 Sf and (t0; g(t0)) 2 Sg and, if they match, compute (t 1 t0; f (t) g(t0)). If f (t) g(t0) k, tuple t 1 t0 is a nogood so it is not stored in Sf+g.
Filtering cost functions consists of anticipating the nogoods on cost functions, removing them before real operation. Imagine that we know that cost function f will be added (in the future) with cost function g, and we know that the set of functions H is a lower bound of g. We de ne the ltering of f from H, noted f H , as f H (t) = f (t) if (Lh2H h(t)) k otherwise f (t) < k Tuples reaching the upper bound k are removed because they will be generate unacceptable tuples when f will be added with g (remember that H is a lower bound of g). This causes to reduce jf j before operating with it.
Let f and g be two cost functions, and G set of functions that is a lower bound of g. Filtering f with G before adding with g it is equal to f + g, To see this result, it is enough to decompose the function f , stored as the set of tuples that do not reach the upper bound k, in the following partition, Sf = f(t1; f (t1))jt1 2 P g [ f(t2; f (t2))jt2 2 Qg f + g = f G + g where P = ftjt 2 Qxi2var(f) D(xi); 9t0 2 Qxj2var(G) D(xj ); t 1 t0 is de ned, such that (Lh2G h(t0)) f (t) < kg, and Q = ftjt 2 Qxi2var(f) D(xi); 8t0 2 Qxj2var(G) D(xj ); t 1 t0 is de ned, such that (Lh2G h(t0)) f (t) kg. Assuming that var(G) = var(g), function f + g is stored as, but the second set is empty because for any t0; f (t2) f (t2) g(t0), since G is a lower bound of g, so f (t2) Then, f + g is stored as, which is exactly f G + g.
How often do we know that function f will be added with function g? In vertex u, function m(u;v) summarizes the e ect of the part of the cluster tree rooted at u, while m(v;u) summarizes the e ect of the rest of the cluster tree. To compute the solution in vertex u, these two functions must be added. Therefore, if we are able to compute a lower bound of m(v;u) before m(u;v) is sent, we can lter m(u;v) with that lower bound and reduce its size.
With this idea, function ltering easily integrates into CTE. A ltering tree-decomposition is a tuple hT; ; ; i, where (u; v) is a set of functions associated to edge (u; v) 2 E with scope included in sep(u; v). (u; v) must be a lower bound of the corresponding m(v;u) (namely, (u; v) m(v;u)). The algorithms CTEf and MCTEf(r) use a ltering tree decomposition. They are equivalent to CTE and MCTE(r) except in that they use (u; v) for ltering functions before computing m(u;v) or M(u;v). For CTEf, we replace line 3 by, 3 m(u;v)
Pf2B f (u;v)[sep(u; v)]; Similarly for MCTEf(r) we replace line 3 by two lines, 3:1 3:2 fP1; :::; Ppg M(u;v)
partitioning(B; r); f(Pf2Pi f (u;v))[sep(u; v) \ ([f2Pi var(f ))] j i : 1:::pg]; An option for CTEf is to include in (u; v) a message M(v;u) from a previous execution of MCTE(r). Applying this idea to MCTEf, we obtain a recursive algorithm which naturally produces an elegant iterative approximating method called IMCTEf (Figure 2). It executes MCTEf(r) using as lower bounds (u; v) the messages M(rv;u1) computed by MCTEf(r 1) which, recursively, uses the messages M(rv;u2) computed by MCTEf(r 2), an so on. procedure IMCTE(hX; D; C; ki, hhV; Ei; ; i) for each (u; v) 2 E do (u; v) := f;g; r := 1; repeat
MCTEf(r); r := r + 1; for each (u; v) 2 E do (u; v) := M(u;v); until exact solution or exhausted resources
The CTE algorithm can be easily adapted to the distributed case, producing the Distributed CTE (DCTE) algorithm. We assume that the DWCSP instance (X; D; C; A; ) to solve is arranged in a cluster tree (T; ; ), where each vertex is a di erent agent (distributed algorithms to build a cluster tree exist, see section 7). Let us consider self , a generic agent. It owns a speci c vertex in the cluster tree, so self knows its position in the tree: it knows its neighboring agents and the separators with them. Besides, self also knows variables of (self ) and cost functions of (self ).
DCTE exchanges messages among agents. There is one message type, CF , to exchange cost functions. When self has received function messages from all its neighbors except perhaps i, it performs the summation of the received cost functions (excluding cost function from i) with the cost functions of (self ), producing a new cost function, which is projected on sep(self; i) and sent to agent i. This process is repeated for all neighbors. Agents having a single neighbor are the rst computing and sending CF messages.
CF messages play the same role as function messages in centralized CTE. For each edge (i; j) in the tree (i and j are neighboring agents) there are two CF messages: one from i to j and other from j to i. Once these two messages have been exchanged for all edges in the tree, agent self contains in its cluster (formed by (self ) and the CF messages received from its neighbors) enough information to solve the particular WCSP instance, assuring that local optimal solutions at di erent vertices are part of a global optimal solution. To break ties, a total ordering on the values of each variable is needed, which has to be common to all agents.
DCTE algorithm appears in Figure 3. It takes as input the tree
decomposition (T; ; ) on the vertex self (as explained in the rst paragraph of
this section), and returns the vertex self augmented with a number of cost
functions, one per neighbor. These new cost functions plus the cost function
of (self ) are enough to compute the local optimal solutions of each vertex
such that they are compatible with solutions of other vertices and share
the global optimum (they form the minimal subproblem, see [
compute separator(self; j); recvCF [j] sentCF [j] false; end false; if neighbors(self ) = fotherg then ComputeSendFunction(self; other); while (:end) do msg getMsg(); if (msg:type = CF ) then NewCostFunction(msg); end ^j2neighbors(self)(sentCF [j] ^ recvCF [j]); compute solution from (self ) [ frecvF unction[j] j j 2 neighbors(self )g; procedure NewCostFunction(msg) recvF unction[msg:sender] msg:f unction; recv[msg:sender] for each j 2 neighbors(self ) s.t. sent[j] = false do if ^i2neighbors(self);i6=jrecv[i] then ComputeSendFunction(self; j); true; procedure ComputeSendFunction(self; dest) f unction Pi2neighbors(self);i6=dest recvF unction[i] + Pf2 (self) f ; sendMsg(self; dest; f unction[separator(self; dest)]); sent[dest] true; is received from neighbor j, it is stored in recvF unction[j] and the boolean recvCF [j] is set to true. When a cost function is sent to neighbor j, the boolean sentCF [j] is set to true.
The main procedure is DCTE, which works as follows. First, some elements of the cluster tree required for self are computed (neighbors(self ), (self ); (self ), separators between self and its neighbors), and some variables (vectors recvCF and sendCF , variable end) are initialized. If self has a single neighbor, other, self does not have to wait for any incoming cost function. So the procedure ComputeSentFunction is called, computing the corresponding summation of functions projected on the separator (Pf2 (self) f )[separator(self; other)], that is sent to agent other. Next, there is a loop that reads a message, processes it and checks the nal condition, when self has received/sent a cost function from/to each neighbor. Finally, the solution is computed using the cost functions in (self ) and the received cost functions.
Procedure NewCostFunction processes CF messages. It records the cost function contained in the message, and if this function allows for computing a cost function to be sent to another neighbor, it is done by the ComputeSentFunction procedure.
DCTE is a distributed synchronous algorithm, since self has to wait to receive CF messages from all its neighbors but j, to be able to compute (and send) its CF message to j.
DCTE can be easily modi ed to produce the Mini-cluster version (DMCTE). We have two new parameters here: r is the maximum arity of the cost functions that can be sent to neighbors, and ub is the initial upper bound.
DMCTE is conceptually close to DCTE, but its practical implementation is more involved. While DCTE adds all cost functions of an agent (no matter the resulting arity), and sends the projection on the separator, DMCTE limits the arity of the resulting cost function. In consequence, DMCTE exchanges cost functions (via CF messages) which are approximations of the exact cost functions (those exchanged by DCTE). When each agent has sent to/received from a CF message to each of its neighbors, these approximate cost functions have been propagated. While this approximation allow for computing an approximate solution at each agent, there is no guarantee that these solutions will be compatible each other (that is, with the same values for common variables in the separators). To assure this, once CF messages have been exchanged, values of common variables in the separators are exchanged via SS messages. If a discrepancy exists, the value coming from the agent with lower id prevails. Finally, a global upper bound is computed by exchanging U B messages, containing the cost of the current solution on the original cost functions of each agent.
DMCTE uses three message types,
CF : cost function messages. They work as the CF messages of the DCTE algorithm, with the following exception. The set of cost functions to be added is partitioned, such that the cost function resulting from the addition of the cost functions of each class do not exceed arity r. Each resulting function is projected on the separator and sent to the corresponding agent. A CF message contains not a single cost function (as in DCTE) but a set of cost functions.
SS: solution separator messages. When self has received all approximate cost functions and computed an approximate solution, it exchanges the values of variables in the separators with its neighbors. The value sent by the agent with lower id prevails. These messages are sent/received following the same strategy as CF messages. U B: upper bound messages. Once a compatible solution has been found, agents exchange the cost of this solution via U B messages.
They are sent/received following the same strategy as CF messages.
We do not provide the DMCTE code due to space limitations. The very same idea of ltering cost functions can be applied to the distributed case. The iterative version of mini-cluster tree elimination can be extended to the distributed case, where messages of the previous iteration are used as lters to the messages of the current iteration.
The DMCTEf(r) algorithm performs ltering when adding cost functions. Its only novelty with respect DMCTE(r) is that new cost functions to be send to other agents j are ltered when they are computed. The Distributed IMCTEf (DIMCTEf) algorithm is a direct extension of IMCTEf (Figure 2) to the distributed case, where previous messages are recorded and used as lters. The upper bound computed at the end of iteration i is used as parameter ub in the next iteration. We do not provide the code of DIMCTEf due to space limitations. 7
Throughout this paper it is assumed the existence of a cluster tree where
the problem instance is arranged. In the centralized case, it is well-known
the existence of algorithms to build such a tree [
Initially, we have (X; D; C; S(k); A; ), where X is the set of variables,
D is the collection of corresponding domains, C is the set of cost functions,
S(k) is a valuation structure, A is a set of agents and is a function that
maps cost functions into agents. We assume that covers the whole set of
agents (if there is some agent without cost function, it is removed from A).
The construction of the cluster tree (T (V; E); ; ) has the following steps
(where 0(v) denotes the initial value of (v)) :
1. The set of vertices is the set of agents.
2. For each vertex u; (u) = ff 2 C j (f ) = ug; 0(u) = [f2 (u)var(f ).
3. Two vertices u and v are considered adjacent if they share one or more
variables, that is, 0(u) \ 0(v) 6= ;. This criterion de nes a graph G.
4. Using a distributed spanning tree algorithm on G [
0(k) ) [ j;k2neighbors(i);j6=k
X Y Z T fXY fYT fTZ U V Z T fTU fUV fVZ {Z T}
which has a clear meaning: if a variable x appears in two neighbors j and k, it must also appear in the vertex itself, to assure connectness. 8
On the instance depicted in Figure 4, with the indicated tree decomposition, we will detail the execution of DCTE, DMCTE and DIMCTE. DCTE. Agent a1 computes function f1 fXY + fY T + fT Z , projects this function on the separator between a1 and a2, and sends the result, f2 = f1[ZT ], to agent a2 in a CF message, Analogously, a2 computes f3 fT U + fUV + fV Z , projects on the separator and sends the result, f4 = f3[ZT ], to a1 in a CF message, Agent a2 receives the CF message sent by a1 and executes the procedure NewCostFunction, storing the received function and calling ComputeSendUB. The very same process happens in a1 when receiving the CF message from a2: NewCostFunction is executed, the received cost function is stored. Now, a1 computes its local optimum using the cost functions ffXY ; fY T ; fT Z ; f4g, obtaining XY ZT bbba. Analogously, a2 computes its local optimum using the cost functions ffT U ; fUV ; fV Z ; f2g, obtaining U V ZT bbba. DMCTE(r = 2). If r = 2, agents cannot compute cost functions of arity greater than 2. Since original cost functions are binary, agents do not perform any addition on them, they just project on the separator and send the resulting cost functions. Thus, a1 computes g1 = fY T [T ] and sends a CF message with g1 and fZT to a2.
Agent a1 computes its local optimum, that is XY ZT bbba, while a2 does the same, obtaining U V ZT bbbb. Since there is discrepancy in the value of T , values of T and Z are exchanged between the agents. Assuming that a2 has smaller identi er than a1, its value for T prevails, so a1 changes its optimum to XY T Z bbbb. Now agents exchange their actual costs on the initial cost functions using U B messages. At the end, each agent knows that a true upper bound of the cost of the exact optimum is 22, the cost of the all b's solution in the whole instance.
DIMCTEf. We take 9 as the limit of the #tuples computed by agent (9 = 23, we use the same memory as DMCTE(r = 3)). Let us start with r = 2 (r = 1 has no sense here because all initial cost functions are binary).
Z a fZT : a b b Analogously, a2 computes g2 = fT U [T ] and g3 = fZV [Z], builds a CF message containing g2 and g3 and sends it to a1.
This is exactly the DMCTE execution indicated above. Then, we move to r = 3 taking as new ub = 22, the upper bound computed in the previous iteration. Agent a1 computes g4 = fXY + fY T , ltering its construction with g2. Then, it computes g5 = g4g2[T ], builds a CF message with g5 and fZT , and sends it to a2. It is worth noting that three tuples are eliminated, since they are nogoods (their cost is higher or equal the current ub). Agent a2 computes g6 = fT U + fUV , ltering with g1 and fZT [T ]. Four tuples are eliminated because their cost reach the upper bound. It computes g7 = g6fg1;fZT [T ]g[T ]. Agent a2 lters fZV with fZT [Z], but no tuple is eliminated. Its projection on Z generates g8 = fZV fZT [Z][Z].
At this point, a1 and a2 compute the approximate optimum in their respective vertices. It happens that a1 computes XY ZT bbba, while a2 computes U V ZT bbba. No discrepancy exists on values of variables in separators, so they exchange U B messages on the cost of the optimum, obtaining 20 as upper bound (in fact, this is the exact optimum).
Then, we move with r = 4, expecting to have enough memory to compute the exact optimum. Agent a1 computes f1 = fXY + fY T + fZT , ltering it with g7 and g8. It happens that all tuples are removed because their cost reach the upper bound. 34 + 2 + 2 34 + 2 + 0 34 + 0 + 2 34 + 0 + 0 28 + 2 + 2 28 + 2 + 0 32 + 0 + 2 32 + 0 + 0 ub ub ub ub ub ub ub ub ub ub ub ub ub This means that the previous approximate solution is in fact the true optimum, and its cost the optimum cost. We observe that in the r = 4 iteration, DIMCTEf uses no extra memory since each tuple is discarded as it is generated. To satisfy the communication protocol, a1 builds a CF message with only the tuple ba with cost 20 for fZT g, and sends it to a2.
Agent a2 computes f3 = fT U + fUV + fZV , ltering with fZT and g5. Then, it computes f5 = f3ffZT ;g5g[ZT ].
All but three tuples are removed because they reach the upper bound. Agent a2 builds a CF message with f5 and sends it to a1. At this point, a1 computes its local optimum XY ZT bbba and a2 does the same U V ZT bbba. There is no need to exchange SS and U B messages, because the problem has been solved exactly. The solution inside each agent is the optimal one.
In this case, DIMCTEf exchanges messages of the same size as DMCTE(r = 3) (maximum of 23 tuples), but it is able to solve exactly this instance, while the exact algorithm DCTE requires larger messages (maximum of 24 tuples). 9
We have presented DCTE, DMCTE and DIMCTEf, distributed synchronous algorithms for solving distributed WCSPs (a more precise version of the wellknown distributed COPs). The DCTE algorithm solves the problem exactly, but requires messages of exponential size. DMCTE and DIMCTEf limit the used memory, at the cost of achieving an approximated solving. Using the function ltering strategy, that also holds in the distributed context, DIMCTEf performs a better memory usage than DMCTE, which increases its practical applicability.
These algorithms are inspired in their centralized counterparts, but their extension requires some care. This is especially true for the DMCTE algorithm that, in addition to the CF message type used for DCTE, requires two new types of messages SS and U B to deal with the subtleties of approximated solving. More work is needed, especially of experimental nature, to assess the practical applicability of the presented algorithms on di erent benchmarks.
Authors thank reviewers for their constructive comments and criticisms.