# optimal_decoupling_in_linear_constraint_systems__8dcd0ef1.pdf

Optimal Decomposition in Linear Constraint Systems

Cees Witteveen and Michel Wilson and Tomas Klos Algorithmics group, Department of Computer and Software Technology, Delft University of Technology, NL-2628 CD, Delft, The Netherlands

Decomposition is a technique to obtain complete solutions by assembling independently obtained partial solutions. In particular, constraint decomposition plays an important role in distributed databases, distributed scheduling and violation detection: It enables conflictfree local decision making, while avoiding communication overloading. One of the main issues in decomposition is the loss of flexibility due to decomposition. Here, flexibility roughly refers to the freedom in choosing suitable values for the variables in order to satisfy the constraints. In this paper, we concentrate on linear constraint systems and efficient decomposition techniques for them. Using a generalization of a flexibility metric developed for Simple Temporal Networks, we show how an efficient decomposition technique for linear constraint systems can be derived that minimizes the loss of flexibility. As a by-product of this decomposition technique, we propose an intuitively attractive flexibility metric for linear constraint systems where decomposition does not incur any loss of flexibility.

Introduction Decomposition is a technique to obtain total solutions by assembling partial solutions. Typically, these partial solutions are obtained by distributed local problem solving and does not require communication between the individual problem solvers. A well-known example is the maintenance of global integrity constraints in distributed databases (Gupta and Widom 1993; Alwan, Ibrahim, and Udzir 2009). If such global integrity constraints would have to be maintained centrally, communication costs would be too high. Decomposition of such global integrity constraints results in the addition of a set of local integrity constraints to each local database (site) in such a way that satisfaction of all the constraints at each site guarantees satisfaction of the global integrity constraint. Another example is peer-to-peer systems and sensor networks, where one is focusing on the detection of constraint violations (Agrawal et al. 2007). Here, constraints define a set of normal states of the total system, and violations of such constraints indicate potential anomalies (e.g., huge file exchanges or extreme sensor readings). In order to detect such anomalies in real time, decomposition is

Copyright c 2014, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

used to establish constraint violations in a distributed way, without the need for communication during detection. Note that these decomposition methods are performed offline and are not meant to improve the efficiency of finding solutions1 online. Instead, they provide a means to distribute a constraint problem over a number of local problem solving processes (sites) such that each site is able to propose its own solution. These partial solutions constitute a set of conflict-free solutions and can be easily merged to create a total solution of the original constraint problem. A major problem in decomposing constraint systems is the loss of flexibility due to decomposition (Hunsberger 2002a; Wilson et al. 2013). Here, flexibility roughly refers to the amount of freedom one has in choosing values for variables to satisfy the constraints. Decomposition, while aiming at providing enough flexibility to the local problem solvers, might seriously affect this flexibility. The effect of decomposition on the flexibility of constraint systems has been studied mainly in the context of Simple Temporal Networks (STNs)2, where these decomposition methods are known as as temporal decoupling methods (Hunsberger 2002b; Boerkoel and Durfee 2012; Brambilla 2010). Currently, the study of flexibility metrics and decoupling methods is restricted to STNs. In this paper, we would like to generalize both the flexibility metrics as well as the decomposition methods to general linear constraint systems such that decomposition now can be applied to a much broader range of applications. In that sense, our work can be seen as an example of a concrete method satisfying the requirements for a general decomposition framework as sketched by Brodsky et al. (Brodsky, Kerschberg, and Varas 2004). As an even more ambitious goal for this paper we aim at a tight integration of decomposition and flexibility computation in one framework. This means not only that we want to use a common (LP-)framework to specify the flexibility of original and decomposed systems, but also that we want to come up with a flexibility metric that allows us to compute an arbitrary decomposition in a very efficient way without any loss of flexibility. Using this (stronger) flexibility met-

1It has been shown that finding a solution of a constraint system is polynomially related to finding a decomposition for it, see (Planken, de Weerdt, and Witteveen 2010). 2STNs (Dechter 2003) constitute a rather restricted subset of linear constraint systems.

Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence

ric, we are able to generalize a quite recent result obtained by (Wilson et al. 2013) to linear constraint systems. Before presenting these results, we start with some preliminaries.

Preliminaries A linear constraint system is a tuple S = (X, C), where X = {x1, . . . , xn} is a set of variables and C is a set of m constraints ci each of the form ai,1x1 + . . . + ai,nxn bi. A linear constraint system is compactly represented by the matrix inequality Ax b where A = [ai,j] is an m n matrix of coefficients, x = [xi]n 1 is an n 1 vector of variables, and b = [bj]m 1 is an m 1 vector of constants. We use the following conventions: Bold-face capital letters refer to matrices, and boldface lower case letters to vectors. Elements of vectors and matrices are referred to by italic lower case letters. If A is an m n matrix, At denotes the n m transpose of A. The rows of A are indicated by ai, i = 1, 2, , . . . m, that is A = [a1, . . . , am]t. A solution σ of a constraint system S is an assignment σ(x) = v of the n 1 vector x of variables to an n 1 vector v of real numbers such that Av b. Equivalently, we will refer to such an assignment σ as a function from X to R. In this paper, we always assume a linear constraint system S to be consistent (there always exist at least one solution σ), and bounded (every solution σ assigns a bounded real value v to a variable x). We will use S = (X, C) or S : Av b to refer to a linear constraint system. In this paper we often refer to Simple Temporal Networks, abbreviated by STNs. An STN S = (X, C) (Dechter, Meiri, and Pearl 1991; Dechter 2003) is a special case of a linear constraint system where every constraint in C is a binary difference constraint xi xj cij for some constant cij R.

Generalizing the STN flexibility metric Instead of a single solution to a constraint system S, we are interested in the flexibility of S. Intuitively, the flexibility of S is related to the freedom we have in choosing values vi to assign to variables xi in solutions σ for S. To introduce such a flexibility metric for linear systems, we first concentrate on STNs, for which a variety of flexibility metrics have been proposed. Considering consistent STNs, it is well-known (Dechter 2003) that for every x X we can find its (unique) minimum3 value est(x) and maximum value lst(x) that can occur in any solution of S = (X, C). Moreover, the set of minimum values and the set of maximum values both constitute a solution to S. Finally, it holds that, for every variable xi X and for every value vi [est(xi), lst(xi)], the assignment xi vi can be extended to a solution of the constraint system. So for every (single!) xi X, we are free to choose any value between est(xi) and lst(xi) without jeopardizing the satisfaction of the constraints.

3STNs are used to specify temporal scheduling problems. Using standard STN-terminology, we use est(x) and lst(x) as familiar notations to indicate the earliest (minimum) and latest (maximum) time value respectively, for the variable x.

These properties justified the idea that the flexibility flex(xi) of a variable xi can be associated with the difference lst(xi) est(xi). Therefore, quite a lot of flexibility metrics for STNs (Hunsberger 2002b; 2002a; Policella et al. 2004; 2005) essentially are based on defining the flexibility flex(S) of the constraint system S as the sum flex(S) =

xi X(lst(xi) est(xi)). We want to obtain a flexibility metric flex(S) for linear constraint systems as a conservative extension of this flexibility metric. The problem, however, when generalizing from STNs to linear systems, is that, in general, the set of maximum (minimum) values for variables does not constitute a solution to S.

Example 1. Consider the system S = (X, C) where X = {x1, x2, x3} and C contains the following linear constraints: xi 0, for i = 1, 2, 3, x1 + x3 50, x2 + x3 50, and x1 x3. The matrix equation corresponding to S is Ax b, where

1 0 0 0 1 0 0 0 1 1 0 1 0 1 1 1 0 1

0 0 0 50 50 0

Observe that the set of individual maxima of the variables (i.e., x1 = 25, x2 = 50, x3 = 50) does not constitute a solution to S. On the other hand, if we would maximize the sum x1+x2+x3 of all variables given Ax b, there is a unique maximum value for this sum (75). Likewise, minimizing this sum given Ax b results in a minimum value (0). Intuitively then, we could define the flexibility of S as the difference between the maximum and the minimum value of this sum. Hence, the resulting flexibility of this system would be 75 0 = 75. There is however, one caveat: obviously, we should ensure that the value of any variable xi in maximising the sum should be at least as large as its value in minimising the sum of variables.

Based on this idea, we propose to define the flexibility flex(S) of a linear system S : Ax b as follows: Consider two vectors of variables x = [x i ]n 1 and x+ = [x+ i ]n 1 and the following LP:

xi X (x+ i x i )

s.t. : Ax b, (1)

Note that a maximizer σ of the LP (1), where σ(x ) = [v i ]n 1 and σ(x+) = [v+ i ]n 1, can also be viewed upon as a set of non-empty4 intervals IX = {[v i , v+ i ] | i = 1, . . . , n} for the variables in X. In fact, IX is a set of intervals with maximum total length, such that both the lower bounds v i of the intervals as well as the upper bounds v+ i constitute a solution to S.

4Observe that consistency an boundedness of S always guarantee the existence of such a set of intervals.

This flexibility metric max

xi X (x+ i x i ) for linear constraint systems constitutes a conservative extension of the flexibility metric flex() defined for STNs:

Proposition 1. Let S : Ax b be an STN. Then for the LP (1) associated with this constraint system, it holds that

xi X (x+ i x i ) =

xi X (lst(xi) est(xi)).

Proof. Observe that

xi X (x+ i x i ) max{

xi X x+ i } min{

xi X lst(xi)

xi X est(xi)

= flex(S). Since S is an STN, both σ+(xi) = lst(xi) and σ (xi) = est(xi), i = 1, . . . , n, are solutions of Ax b. Hence, max

xi X (x+ i x i ) = xi X (lst(xi) est(xi)) = flex(S).

Every variable xi X in an STN S enjoys the property5 that, for every value vi [est(xi), lst(xi)], the assignment σ(xi) = vi is extendable to a complete solution σ of S. For maximizers of linear systems using the LP (1) the same property holds:

Proposition 2. Let vt = [(v )t, (v+)t] be a maximizer of the LP (1). Then for every xi X and every vi [v i , v+ i ], there exists a solution σ for Ax b such that σ(xi) = vi.

Proof. Note that both v and v+ are solutions of Ax b. Clearly, vi [v i , v+ i ] implies vi = λv+ i + (1 λ)v i for some 0 λ 1. Since every convex combination of solutions of an LP is a solution as well, it follows that σ(x) = λv+ + (1 λ)v is a solution of Ax b, extending σ(xi) = vi.

Decomposition in linear constraint systems Often, constraint problems have to be solved in a distributive context (see e.g. (Hunsberger 2002b; Boerkoel and Durfee 2013)) where communication between the problem solvers is not possible. We consider the case that the set X of variables in S = (X, C) is partitioned into k disjoint subsets Xi, each of them controlled by an independent agent. Besides Xi, such an agent also is given a set of local constraints Ci. While the task of each agent is to find a solution σi for its local constraint system Si = (Xi, Ci), as designers of the distributed system we have to make sure that the merge6

σ = k i=1 σi of these partial solutions σi is a solution of the original system S, whatever choices are made for these σi. Then the flexibility-maximizing decomposition problem for constraint systems is the following problem:

5Intuitively, this property guarantees that [est(xi), lst(xi)] does not contain useless values. 6Think of the merge k i=1 σi as an assembling function σ such that for j = 1, . . . , n, σ(xj) is the value assigned by the agent controlling xj.

Given a constraint system S = (X, C) and a partitioning {Xi}k i=1 of X, how to come up with suitable constraint sets Ci for the subsets Xi such that (i) whatever solutions σi for the subsystems Si = (Xi, Ci) are chosen, their merge σ = k i=1 σi is always a solution for the original system S, while (ii) the total flexibility k i=1 flex(Si) of the distributed system is maximized. For STNs Hunsberger (Hunsberger 2002b) approached this problem by making a distinction between intra-agent constraints, involving variables belonging to a single agent and inter-agent constraints, involving variables controlled by different agents. Then he proposed so-called temporal decoupling algorithms that, by tightening intra-agent constraints, make the set of inter-agent constraints obsolete. As a result, a set of decomposed subsystems Si is returned such that each combination of solutions σi for these subsystems Si can be merged into a complete solution of the original problem. Hunsberger observed that in some cases the added (tightened) constraints may severely limit the flexibilities of the individual subproblems, i.e., the sum k j=1 flex(Sj) of the flexibilities of the subsystems Sj could be considerably less than the flexibility flex(S) of the original system. Therefore, he proposed an algorithm that ensures a locally optimal decoupling, i.e., a decoupling such that no individual constraint can be loosened without violating the property of inducing a decoupling. However, instead of locally optimal decompositions, we want to establish globally optimal decomposition methods not restricted to STNs, but applicable to linear constraint systems. To model this idea of decomposition, without loss of generality, we may assume that the variables x occurring in a (consistent and bounded) linear constraint system Ax b are partitioned into a set of k vectors yi of variables such that [yt 1, . . . , yt k] = xt. This corresponds to creating a partitioning of the set of variables X. The flexibility-maximizing decomposition problem for a linear constraint system S then is to find k matrices Ai and k vectors b j such that

1. for j = 1, . . . , k, Sj : Ajyj b j is a linear constraint system, and 2. whenever σi(yj) = vj is a solution to Sj, the solution σ defined by σ(x)t = [σ(v1)t, . . . , σ(vk)t] is a solution to Ax b, and

3. the sum k j=1 flex(Sj) is maximal.

Example 2. Assume that in the constraint system discussed in Example 1, we have two agents, one controlling the variables x1 and x2, and the other the variable x3. Then y1 = [x1, x2] and y2 = [x3]. Consider the decomposition {S1 : A1y1 b 1, S2 : A2y2 b 2} of S where

1 0 0 1 1 1

, y1 = x1 x2

, y2 = [x3] , b 2 = 25 25

Clearly, the merge of any pair of solutions σ1 and σ2 of these partial systems constitutes a solution to the total system. But

this decomposition comes with a high price: the total flexibility of these two systems equals 25 + 0 = 25, that is one-third of the original flexibility. The question then arises whether this decomposition is a maximally-flexible one.

Like Hunsberger, in linear constraint systems with a partitioning [yt 1, . . . , yt k] = xt of X we also distinguish intraand inter-agent constraints: 1. An intra-agent constraint ci Intra(C) is any constraint ci : aix bi such that for all ai,h = 0 the corresponding variables xh belong to a single block yj. For example, the first three constraints in A (see Example 1) are intra-agent constraints. 2. If ci : aix bi contains variables xh and xh that (i) belong to different blocks of variables yj and yj , respectively, while (ii) ai,h = 0 and ai,h = 0, then ci Inter(C) is said to be an inter-agent constraint. For example, the last three constraints in A are inter-agent constraints. The idea of decomposition is to provide an additional set of intra-agent constraints such that all inter-agent constraints are implied. To see how this can be realised, consider the LP (1) for flexibility maximization. A maximizer of this LP consists of vectors v and v+. Let IX = {[v i , v+ i ] | xi X]} be the corresponding set of intervals. From Proposition 2 we know that, for every single xi, every value vi [v i , v+ i ] can be chosen without jeopardizing the satisfaction of any of the constraints. This property, however is no longer sufficient in a decomposed system: In a decomposed system agents might choose an arbitrary value for a variable xi in its variable block yj concurrently and independently from the others. So, instead of extending an assignment for a single choice, we now have to be prepared for extending an assignment for several concurrent choices to a total solution. Hence, the set IX of intervals has to satisfy an additional requirement: every inter-agent constraint ci has to be satisfied whatever choices vj in the intervals [v j , v+ j ] have been made by the individual agents. So suppose the ith constraint is an inter-agent constraint ci Inter(C) and equals aix = ai,1x1 + . . . + ai,mxm bi Then it should hold that aix bi x [v x v+] But that means that such a set of flexibility-maximizing intervals {[v i , v+ i ]}n i=1 can be derived from a maximizer of the following LP:

xi X (x+ i x i )

s.t. : Ax b, (2)

aix bi x [x x x+] ci Inter(C),

Here, as indicated in the preliminaries, ai denotes the i-th row of A and bi refers to the i-th entry of b. Clearly, the occurrence of an infinite set of constraints in the LP (2) prevents an efficient computation of the maximum

flexibility. Fortunately, there is an easy way to remove these infinite sets of constraints by showing that one extremal solution to the constraint Aix bi implies the existence of solutions for all points x x x+: Proposition 3. Let σ(x)t = [(v )t, (v+)t] be a maximizer of the LP (2) and let ci : aix bi be a linear constraint. Define the vector v i = [v i,j]n 1 such that for every j = 1, . . . , n,

v+ j , if ai,j > 0 v j , if ai,j 0.

Then aiv i bi iff aiv bi, v[v v v+] .

Proof. The only-if direction is obvious since, by definition, v v i v+. Conversely, assume that aiv i bi and let v = [vj] be an arbitrary vector such that v v v+. Without loss of generality, we may assume that there exists a 0 k m such that ai,j > 0 for 1 j k and ai,j 0 for m j > k. Then it holds that m

j=1 ai,jv+ j +

j=k+1 ai,jv j =

j=1 ai,jv i,j bi

Hence, σ(x) = v satisfies the constraint ci, too.

As a consequence, we can replace the infinite set of equations belonging to an inter-agent constraint in LP (2) by one single constraint, resulting in the following LP equivalent to LP (2): max

xi X (x+ i x i )

s.t. : Ax b, (3)

Ax+ b, aix i bi ci Inter(C),

x x+. Here,7 x i is defined analogously to v i . Example 3. Consider the constraint system discussed in Example 1, with the partitioning y1 = [x1, x2] and y2 = [x3]. Using the matrix A derived in Example 1, we can compute the flexibility of the decomposition of S by computing:

xi X (x+ i x i )

s.t. : Ax+ b,

x+ 1 + x+ 3 50,

x+ 2 + x+ 3 50,

x+ 1 x 3 0,

x x+. The flexibility of this system is 50. A maximizer is vt = [(v )t, (v+)t] = [[0, 0, 25]t, [25, 25, 25]t]. Note that this (maximal) flexibility of this decomposition is larger than the flexibility of the decomposition discussed in Example 2.

7Note that both aix+ bi and aix bi occurring in Ax+ b and Ax b, respectively, are implied by aix bi.

One of our goals in this paper is not only to compute the maximum flexibility of a decomposed system, but also to compute an optimal decomposition realizing this maximum flexibility. One of the nice features of our framework is that, once we have determined the flexibility of a decomposed system, the decomposition itself can be easily derived from the solution of the LP (3), as we will show in the next section.

How to decompose a linear constraint system To compute an actual decomposition of a linear constraint system S : Ax b using a partitioning [yt 1, . . . , yt k] = xt of x, we need to specify a decomposition {Sj : Ajyj b j}k j=1 with the required properties as mentioned before. To obtain this decomposition, we first solve the LP (3) and then use a maximizer vt = [(v )t, (v+)t] for this LP to obtain the decomposition as follows: Using the partitioning [yt 1, . . . , yt k] = xt of x, every constraint ci : aix bi in S can be written as: aix = a(i,1)y1 + . . . + a(i,k)yk bi where ai = [a(i,1), . . . , a(i,k)] is the i-th row of A. Since vt = [(v )t, (v+)t] is a maximizer for LP (3), it holds that aiv i bi, where v i = [v i,j] is defined as:

v+ j , if ai,j > 0 v j , if ai,j 0.

Let us partition the vector v i into [v i,1, v i,2, . . . , v i,k]t according to the partitioning of x. Then aiv i can be written as aiv i = a(i,1)v i,1 + . . . + a(i,k)v i,k bi (4) Using this equation, we replace the inter-agent constraint ci : aix bi by a set of intra-agent constraints as follows: For every vector yj, create the constraint a(i,j)yj b i,j (5) where b i,j = a(i,j)v i,j and add this constraint to Sj. Applying this procedure for all constraints results in a set of subsystems {Ajyj b j}k j=1 derived from Ax b. Note that some of these constraints might be trivial if all the coefficients in a row of Aj are 0. Therefore, these constraints (rows) can be omitted. It is easy to see that this set {Ajyj b j}k j=1 is a decomposition of S : Ax b: For j = 1, . . . , k, let σj(yj) be an arbitrary solution to the subsystem Sj : Ajyj b j. Finally, let σ(x) be the merge of all the solutions σj(yj). We have to show that σ(x) is a solution of the original system S. Consider an arbitrary constraint ci : aix bi of S. By construction, for j = 1, . . . , k there exist constraints ci,j : a(i,j)yj b i,j in Sj such that a(i,j)σj(yj) b i,j and b i,j = a(i,j)v j. Hence, since σ is the merge of the local solutions σj:

j=1 a(i,j)σj(yj)

j=1 b i,j =

j=1 a(i,j)v i,j bi

where the last inequality holds by the inequalities (4) and (5). Hence, the merge σ(x) of all solutions σj(yj) satisfies ci.

Example 4. Continuing Example 3, consider a maximizer v = [0, 0, 25]t and v+ = [25, 25, 25]t for a decomposition of S. Using this maximizer, the constraints x1 0, x2 0 are added to S1, and x3 0 is added to S2. The constraint x1 +x3 50 is split into two constraints x1 25 and x3 25. These are added to S1 and S2, respectively. Likewise, x2 + x3 50 is split into x2 25 and x3 25. Finally, x1 x3 is split into x1 25 and x3 25. The outcome of this procedure is the following decomposition [A1y1 b 1, A2y2 b 2] of S where

1 0 0 1 1 0 0 1

, y1 = x1 x2

, y2 = [x3] , b 2 = 25 25

Although the procedure specified above results in a decomposition of the original system Ax b, we also have to show that it results in a flexibility-maximizing decomposition, i.e., the sum of the flexibilities flex(Si) of the subsystems equals the flexibility as computed by the LP (3). So let S = (X, C) be partitioned by {Xj}n j=1. Let F be the maximum flexibility of this system as computed by the LP (3) and vt = [(v )t, (v+)t] be a corresponding maximizer. Let the resulting decomposition using vt be {Sj : (Xj, Cj)}k j=1 = {Sj : Ajyj b j}k j=1. We show that k j=1 flex(Sj) = F, where flex(Sj) is the maximum flexibility computed using the original LP (1) for Ajyj b j.

1. k j=1 flex(Sj) F. Note that k j=1 flex(Sj) =

flex(S ) where S = (X, k j=1 Cj) and the flexibility is computed using LP (1). Let F be the flexibility of S computed with the LP (3). Since there are no interagent constraints, in this case LP (3) is equivalent to the LP (1), hence flex(S ) = F . Now consider S = (X, k j=1 Cj C) with the same partitioning {Xj}n j=1 as S and let LP (3) compute its maximum flexibility F . On one hand, since every constraint in C is either equal to a constraint in k j=1 Cj or implied by it, it should hold

that F = F . On the other hand, k j=1 Cj C contains C, and, since the partitioning is identical, F F. Therefore, we have k j=1 flex(Sj) = flex(S ) = F = F F.

2. F k j=1 flex(Sj) Consider the maximizer vt = [(v )t, (v+)t] for the LP (3) applied to S. For j = 1, . . . , k, let vt j = [(v j )t, (v+ j )t] be the parts of the maximizer corresponding to the partitioning of x. We show that, for j = 1, . . . , k, both v j and v+ j are solutions to Ajyj b j. This is easy to see since

Ajv j Ajv j b j and Ajv+ j Ajv j b j.

So, for j = 1, . . . , k, flex(Sj)

xij Xj(v+ ij v ij).

Summing up, we derive

j=1 flex(Sj)

xij Xj (v+ ij v ij) = F.

A strong flexibility metric

In the LP (3) every inter-agent constraint aix bi entails two constraints aix+ bi and aix bi occurring in Ax+ b and Ax b, respectively. Hence, these constraints can be removed from the LP-specification without affecting the solution. As a limiting case then, when the (finest) partitioning of the variables results in n blocks containing only one variable xi, the LP-specification obtained from LP (3) is:

xi X (x+ i x i )

s.t. : aix i bi i = 1, 2, . . . m, (6)

Defining the matrices A+ = [a+ i,j] and A = [a i,j] by

a+ i,j = ai,j if ai,j > 0 0 else a i,j = ai,j if ai,j < 0 0 else we can easily rewrite this LP to the following simple LP:

xi X (x+ i x i )

s.t. : A+x+ + A x b, (7)

Let us denote the flexibility of a constraint system S computed for the finest partition {xi}n i=1 by flex (S), i.e., flex (S) is the outcome of solving LP (7). This metric exhibits a stronger property than the weak flexibility metric flex(S) we have discussed before: Consider the set of intervals {[v i , v+ i ]}n i=1 generated by a maximizer vt = [(v )t, (v+)t] for LP (7). This metric not only assures that for every single variable xi every value vi in the interval [v i , v+ i ] can occur in a solution σ, but also that this property holds for any concurrent choice of values for a set of variables: For any subset X X of variables, values vi in the intervals [v i , v+ i ] might be chosen simultaneously without jeopardizing the satisfaction of all the constraints:

Proposition 4. Let S : Ax b be a constraint system with the finest partitioning X = {xi}n i=1. Let vt = [(v )t, (v+)t] be a maximizer for the LP (7). Then for every v such that v v v+, it holds that Av b.

Proof. Let v be such that v v v+. Then we have Av = A+v + A v A+v+ + A v b.

Therefore, we call flex () a strong flexibility metric. As the careful reader might have noticed, we can easily show that an optimal decomposition of linear constraint systems does not need to result in any loss of flexibility using this strong flexibility metric flex ():

Proposition 5. Let S be a linear constraint system Ax b and let [y1, . . . , yk] be a partitioning of x. Then there exists a decomposition {Sj}k j=1 of S according to [y1, . . . , yk] such that flex (S) = k j=1 flex (Sj).

Proof. Consider a maximum-flexibility decomposition {Sxi}n i=1 induced by the finest partitioning {xi}n i=1 of X using the LP (7). For i = 1, . . . n, let Sxi = ({xi}, Cxi). It follows that flex (S) = n i=1 flex (Sxi). Since {Sxi}n i=1 is a decomposition, a decomposition induced by [y1, . . . , yk] can be obtained by taking Sj = (Xj,

xi Xj Cxi) for j = 1, . . . , k, where Xj is the set of variables occurring in yj. The resulting (strong) flexibility of the decomposed system induced by {Xj}k j=1 now equals

j=1 flex (Sj) =

xi Xj flex (Sxi)

i=1 flex (Sxi) = flex (S).

Hence, there exists at least one decomposition realizing a total flexibility equal to the original flexibility flex (S).

This result generalizes a recent result obtained by (Wilson et al. 2013) for STNs to linear constraint systems.

Conclusion and Discussion In this paper we concentrated on the decomposition of linear constraint systems. We introduced a generalisation flex() of a flexibility metric proposed for STNs and used this metric to compute a maximum-flexible decomposition of a linear constraint system induced by a partitioning of the set of variables. Using an LP-approach, we finally proposed a strong flexibility metric flex () as an alternative to the flexibility metric derived from STNs. We showed that using this strong flexibility metric, an arbitrary decomposition of a linear constraint system can be achieved without any loss of flexibility. We remark that the ratio flex(S)/flex (S) of these flexibility metrics indicates how much dependencies there exist between the variables X in S: whenever this ratio is close to one, the values of variables within the intervals determined by the flex metric can be chosen almost independently, while a large ratio indicates that choosing a value within an interval can heavily influence the choice of values for other variables. Geometrically, flex(S) determines the smallest box containing the polyhedron associated with S while flex (S) determines the largest box contained in the polyhedron determined by S. Finally, we would like to remark that LP (7) can also be used outside a decomposition setting: Given an arbitrary LP with objective function max f(x) resulting in a maximum m, we can add an additional constraint in the form of f(x) m to the set of constraints. Then applying LP (7) to the resulting system and using a maximizer vt = [(v )t, (v+)t] to obtain a set of intervals {[v i , v+ i ]}n i=1, we know which values for the individual variables xi do not affect the maximum value m. This provides a way to obtain flexible solutions to LP-problems.

Acknowledgments The authors thank the anonymous reviewers for their constructive remarks and well-considered suggestions for improvement of the paper.

References Agrawal, S.; Deb, S.; Naidu, K. V. M.; and Rastogi, R. 2007. Efficient detection of distributed constraint violations. In Proceedings of the 23rd International Conference on Data Engineering (ICDE 2007), April 15-20, 2007, Istanbul, Turkey, 1320 1324. IEEE. Alwan, A.; Ibrahim, H.; and Udzir, N. I. 2009. Improved integrity constraints checking in distributed databases by exploiting local checking. Journal of Computer Science and Technology 24(4):665 674. Boerkoel, J., and Durfee, E. 2012. A distributed approach to summarizing spaces of multi-agent schedules. In Proceedings of the 26th AAAI Conference on Artificial Intelligence (AAAI-12), 1742 1748. AAAI Press, Menlo Park, CA. Boerkoel, J., and Durfee, E. 2013. Distributed reasoning for multi-agent simple temporal problems. Journal of AI Research 47:95 156. Brambilla, A. 2010. Artificial Intelligence in Space Systems: Coordination Through Problem Decoupling in Multi-Agent Planning for Space Systems. Lambert Academic Publishing. Brodsky, A.; Kerschberg, L.; and Varas, S. 2004. Optimal constraint decomposition for distributed databases. In Maher, M., ed., Advances in Computer Science - ASIAN 2004. Higher-Level Decision Making, volume 3321 of Lecture Notes in Computer Science, 301 319. Springer Berlin Heidelberg. Dechter, R.; Meiri, I.; and Pearl, J. 1991. Temporal constraint networks. Artificial Intelligence 49(1-3):61 95. Dechter, R. 2003. Constraint Processing. Morgan Kaufmann. Gupta, A., and Widom, J. 1993. Local verification of global integrity constraints in distributed databases. SIGMOD Rec. 22(2):49 58. Hunsberger, L. 2002a. Algorithms for a temporal decoupling problem in multi-agent planning. In Proceedings of the Association for the Advancement of Artificial Intelligence (AAAI-02), 468 475. Hunsberger, L. 2002b. Group Decision Making and Temporal Reasoning. Ph.D. Dissertation, Harvard University, Cambridge, Massachusetts. Planken, L.; de Weerdt, M.; and Witteveen, C. 2010. Optimal temporal decoupling in multiagent systems. In Vander Hoek; Kaminka; Lesperance; Luck; and Sen., eds., Proceedings of the Ninth International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS-10), 789 796. Policella, N.; Smith, S. F.; Cesta, A.; and Oddi, A. 2004. Generating robust schedules through temporal flexibility. In Zilberstein, S.; Koehler, J.; and Koenig, S., eds., Proceedings of the 14 International Conference on Automated Planning & Scheduling (ICAPS 04), 209 218.

Policella, N.; Wang, X.; Smith, S.; and Oddi, A. 2005. Exploiting temporal flexibility to obtain high quality schedules. In Proceedings of the 20th National Conference on Artificial Intelligence (AAAI-05), 1199 1204. AAAI Press, Menlo Park, CA. Wilson, M.; Klos, T.; Witteveen, C.; and Huisman, B. 2013. Flexibility and decoupling in the Simple Temporal Problem. In Rossi, F., ed., Proceedings of the 23th International Joint Conference on Artificial Intelligence (IJCAI-2013), 2422 2428. AAAI Press, Menlo Park, CA.