A Maximal Tractable Class of Soft Constraints

1 Introduction

The constraint satisfaction framework is widely acknowl­ edged as a convenient and efficient way to model and solve a wide variety of problems arising in Artificial Intelligence, in­ cluding planning and scheduling, image processing and natu­ rallanguage understanding.

In the standard framework a constraint is usually taken to be a predicate, or relation, specifying the allowed combina­ tions of values for some fixed collection of variables: we will refer to such constraints here as crisp constraints. A num­ ber of authors have suggested that the usefulness of the con­ straint satisfaction framework could be greatly enhanced by extending the definition of a constraint to include also soft constraints, which allow different measures of desirability to be associated with different combinations of values [Bistarelli eta/., 1999]. In this extended framework a constraint can be seen as a function, mapping each possible combination of values to a measure of desirability or undesirability. Finding a solution to a set of constraints then means finding an as­ signment of values to all of the variables which has the best overall combined desirability measure.

Example 1.1 For example, consider an optimization prob­ lem where we have 2n variables, v1 , v2, ... , v2n, and we wish to assign each variable an integer value in the range 1, 2, ... , n, subject to the following restrictions :

• Each variable v; should be assigned a value that is as close as possible to i/2.
• Each pair of variables v;, v2; should be assigned a pair of values that are as similar as possible.

To model this situation we might impose the following soft constraints:

• A unary constraint on each v; specified by a function '1/J;, where '1/J;(x ) = lx- i/2lr for some r 2: 1.
• A binary constraint on each pair v; , v2; specified by a function 8r, where 8r(x, y) = lx- Ylr for some r 2: 1.

We would then seek an assignment to all of the variables which minimizes the sum of these constraint functions,

The cost of allowing additional flexibility in the specification of constraints, in order to model requirements of this kind, is generally an increase in computational difficulty. In the case of crisp constraints there has been considerable progress in identifying classes of constraints which are tractable, in the sense that there exists a polynomial time algorithm to deter­ mine whether or not any collection of constraints from such a class can be simultaneously satisfied [Feder and Vardi, 1998; Jeavons et a!., 1997]. In the case of soft constraints there has been a detailed investigation of the tractable cases for Boolean problems (where each variable has just 2 possible values) [Creignou eta/., 2001], but very little investigation of the tractable cases over larger domains 1 , even though there are many significant results in the literature on combina­ torial optimization which are clearly relevant to this ques­ tion [Nemhauser and Wolsey, 1988].

In this paper we make use of the idea of a submodular func­ tion [Nemhauser and Wolsey, 1988; Topkis, 1978] to iden­ tify a general class of soft constraints for which there exists a polynomial time solution algorithm. Submodular functions are usually defined as real-valued functions on Boolean tu­ ples (=sets) [Nemhauser and Wolsey, 1988], but we consider the more general case of functions on tuples over an arbitrary finite domain. We also allow our functions to take infinite values. By establishing a new decomposition result for this general class of binary submodular functions (Theorem 4.4), we obtain a cubic time algorithm to find the optimal assign­ ment for any set of soft constraints defined by such functions.

1 The only previous work we have been able to find on non­ Boolean tractable soft constraints is [Khatib et a/., 2001], which describes a family of tractable soft temporal constraints.

We give a number of examples to illustrate the many dif­ ferent forms of soft constraint that can be defined using bi­ nary submodular functions, and we also show that this class is maximal, in the sense that no other form of binary constraint can be added without sacrificing tractability.

2 Definitions

To identify a tractable class of soft constraints we will need to restrict the set offunctions that are used to specify constraints. Such a restricted set of possible functions will be called a soft constraint language.

Definition 2.1 Let D and E be fixed sets. A soft constraint language over D with evaluations in E is defined to be a set of functions, f, such that each ¢> E f is a function from Dk toE, for some k E N, where k is called the arity of ¢>.

For any given choice of soft constraint language, r , we define an associated soft constraint satisfaction problem, which we will call sCSP(r), as follows .

Definition 2.2 Let r be a soft constraint language over D with evaluations in E. An instance P of sCSP(f) is a triple (V, D, C ), where:

• V is a finite set of variables, which must be assigned values from the set D.
• Cis a set of soft constraints. Each c E Cis a pair (cr, ¢) where: cr is a list of variables, called the scope of c; and ¢> is an element of r of arity lcrl, called the evaluation function of c.

Note that, for any constraint c = (cr, ¢ ),the arity of the con­ straint is given by lcrl, the length of the constraint scope. The evaluation function ¢> will be used to specify some measure of desirability or undesirability associated with each possible tuple of values over cr.

To complete the definition of a soft constraint satisfac­ tion problem we need to define how the evaluations obtained from each evaluation function are combined and compared, in order to define what constitutes an optimal overall solu­ tion. Several alternative mathematical approaches to this is­ sue have been suggested in the literature:

• In the semiring based approach [Bistarelli et a/., 1999], the set of possible evaluations, E, is assumed to be an algebraic structure equipped with two binary operations, satisfying the axioms of a semiring.
• In the valued CSP approach [Bistarelli eta!., 1999], the set of possible evaluations E is assumed to be a totally ordered algebraic structure with a top and bottom ele­ ment and a single monotonic binary operation known as aggregation.

For our purposes in this paper we require the same proper­ ties as the valued CSP approach, with the additional require­ ment that the aggregation operator has a partial inverse (so that any evaluation can be "subtracted" from any larger eval­ uation). For concreteness, we shall simply assume through­ out this paper that the set of evaluations E is either the set of non-negative integers together with infinity, or else the set of non-negative real numbers together with infinity. Hence, for any two evaluations PI , P2 E E , the aggregation of PI and P2 is given by PI + P2 E E, and when PI ;::: P2 we also have PI - P2 E E. (Note that we set oo - oo = oo).

The elements of the set E will be used to represent dif­ ferent measure of undesirability, or penalties, associated with different combinations of values. This allows us to complete the definition of a soft constraint satisfaction problem with the following simple definition of a solution to an instance.

Definition 2.3 For any soft constraint satisfaction problem instance P = (V, D, C), an assignment for Pis a mapping t from V to D. The evaluation of an assignment t, denoted if.>p(t), is given by the sum (i .e., aggregation) of the evalua­ tions for the restrictions oft onto each constraint scope, that is,

A solution to P is an assignment with the smallest possible evaluation, and the question is to find a solution.

Example 2.4 For any standard constraint satisfaction prob­ lem instance P with crisp constraints, we can define a corresponding soft constraint satisfaction problem instance P in which the range of the evaluation functions of all the con­ straints is the set {0, oo }. For each crisp constraint c ofP, we define a corresponding soft constraint c of P with the same scope; the evaluation function of c maps each tuple allowed by c to 0, and each tuple disallowed by c to oo.

In this case the evaluation of an assignment t for P equals the minimal possible evaluation, 0, if and only ift satisfies all of the crisp constraints in P. 0

Note that the problem of finding a solution to a soft con­ straint satisfaction problem is an NP optimization problem, that is, it lies in the complexity class NPO (see [Creignou et al., 2001] for a formal definition of this class). If there exists a polynomial-time algorithm which finds a solution to all instances of sCSP(r), then we shall say that sCSP(f) is tractable. On the other hand, if there is a polynomial-time re­ duction from some NP-complete problem to sCSP(r), then we shall say that sCSP(r) is NP-hard.

Example 2.5 Let r be a soft constraint language over D, where IDI = 2. In this case sCSP(f) is a class of Boolean soft constraint satisfaction problems.

If we restrict r even further, by only allowing functions with range {0, oo }, as in Example 2.4, then sCSP(f) corre­ sponds precisely to a standard Boolean crisp constraint sat­ isfaction problem. Such problems are sometimes known as GENERALIZED SATISFIABILITY problems [Schaefer, 1978]. The complexity of sCSP(f) for such restricted sets r has been completely characterised, and the six tractable cases have been identified [Schaefer, 1978; Creignou eta!., 200 1].

Alternatively, if we restrict f by only allowing functions with range {0, 1 }, then sCSP(f) corresponds precisely to a standard Boolean maximum satisfiability problem, in which the aim is to satisfy the maximum number of crisp constraints. Such problems are sometimes known as MAX-SAT prob­ lems [Creignou et al., 2001]. The complexity of sCSP(f) for such restricted sets r has been completely characterised, and the three tractable cases have been identified (see Theo­ rem 7.6 of[Creignou et al., 2001]).

We note, in particular, that when f contains just the single binary function ¢xoR defined by

then sCSP(f) corresponds to the MAX-SAT problem for the exclusive-or predicate, which is known to be NP-hard (see Lemma 7.4 of [Creignou eta!., 2001]). 0

Example 2.6 Let r be a soft constraint language over D, where JDI ~ 3, and assume that r contains just the set of all unary functions, together with the single binary function ¢ EQ defined by

Even in this very simple case it can be shown that sCSP(f) is NP-hard [Cohen et al., 2002], by reduction from the MINIMUM MULTITERMINAL CUT problem [Dahlhaus eta/., 1994]. 0

The examples above indicate that generalizing the constraint satisfaction framework to include soft constraints does indeed increase the computational complexity, in general. For exam­ ple, the standard 2-SATISFIABILITY problem is tractable, but the soft constraint satisfaction problem involving only the sin­ gle binary Boolean function, ¢xoR, defined at the end of Ex­ ample 2.5, is NP-hard. Similarly, the standard constraint sat­ isfaction problem involving only crisp unary constraints and equality constraints is clearly trivial, but the soft constraint satisfaction problem involving only soft unary constraints and a soft version of the equality constraint, specified by the func­ tion ¢EQ defined at the end of Example 2.6, is NP-hard.

However, in the next two sections we will show that it is possible to identify a large class of functions for which the corresponding soft constraint satisfaction problem is tractable.

3 Generalized interval functions

We begin with a rather restricted class of binary functions, with a very special structure.

Definition 3.1 Let D be a totally ordered set. A binary func­ tion, ¢ : D 2 --+ E will be called a generalized interval func­ tion on D if it has the following form:

for some a, b E D and some p E E. Such a function will be denoted 77[a,bj.

We can explain the choice of name for these functions by con­ sidering the unary function 77[a,bj ( x, x). This function returns the value p if and only if its argument lies in the interval [a, b]; outside of this interval it returns the value 0.

We shall write r GI to denote the set of all generalized in­ terval functions on D, where D = {1, 2, ... , M} with the usual ordering.

The main result of this section is Corollary 3.6, which states that sCSP(f GI) is tractable. To establish this result we first define a weighted directed graph 2 associated with each instance of sCSP(f GI ).

Definition 3.2 Let P = (V, {1, ... , M}, C) be an instance of sCSP(f GI ). We define the weighted directed graph Gp as follows.

• The vertices of Gp are as follows:

• The edges of Gp are defined as follows:
• For each v E V, there is an edge from S to VM with weight oo;
• For each v E V, there is an edge from v0 toT with weight oo;
• For each v E V and each d E {1, 2, ... , M - 2}, there is an edge from Vd to vd+l with weight oo;
• For each constraint ( ( v, w), 77[a,bj) E C, there is an edge from Wb to Va-l with weight p. These edges are called "constraint edges".

Examp1e3.3 Let P = ({x,y,z},{1,2,3,4},C) be an in­ stance of sCSP(f GI) with the following four constraints:

The corresponding weighted directed graph Gp, is shown in ~gure1. 0

2 This construction was inspired by a similar construction forcer­ tain Boolean constraints described in [Khanna eta/., 2000].

Any set of edges C in the graph Gp whose removal leaves the vertices S and T disconnected will be called a cut. If every edge in C is a constraint edge, then C will be called a proper cut. The weight of a cut C is defined to be the sum of the weights of all the edges in C.

Example 3.4 Consider the graph Gp shown in Figure 1. The set { (y3 , z0 )} is a proper cut in Gp with weight 7, which is minimal with respect to inclusion. The set {(x4,y2), (z3,y3)} is a proper cut in Gp with weight 5, which is again minimal with respect to inclusion. 0

Proposition 3.5 Let P be any instance of sCSP(r GI ), and let Gp be the corresponding weighted directed graph.

1. For each minimal proper cut in Gp with weight <P, there is an assignment for P with evaluation <P.
2. For each assignment t for P with evaluation <P, there is a proper cut in Gp with weight <P.

Proof:

1. Let C be any minimal proper cut of the graph Gp, and let Cs be the component of Gp \ C connected to S . Define the assignment tc as follows:

(Note that tc is well-defined because Cs always con­

tains v M, and never contains v0 , by construction.)

By the construction of Gp , it follows that:

Now consider any constraint c = ((v,w),7J[a,b]) ofP, and its associated edge e in Gp. By the definition of generalized interval constraint and the choice of tc, 7J[a ,b](tc(v), tc(w)) = p if and only if va-l rf. Cs and wb E C s, and hence if and only if e joins a vertex in C s to a vertex not in C s . Since C is minimal, this happens if and only if e E C. Hence, the total weight of the cut C is equal to the evaluation of tc.

1. Conversely, lett be an assignment toP, and let K be the
2. set of constraints in P with a non-zero evaluation on t . Now consider any path from S toT in Gp. If we ex­ amine, in order, the constraint edges of this path, and assume that each of the corresponding constraints eval­ uates to 0, then we obtain a sequence of assertions of the following form:

Since the second disjunct of each assertion contradicts the first disjunct of the next, these assertions cannot all hold simultaneously, so one of the corresponding con­ straints must in fact give a non-zero evaluation on t. Hence, every path from S toT includes at least one edge corresponding to a constraint from K, and so the edges corresponding to the set K form a cut in Gp. Further­ more, by the choice of K, the weight of this cut is equal to the evaluation oft.

D

Hence, by using a standard efficient algorithm for the MIN­ IMUM WEIGHTED CUT problem [Goldberg and Tarjan, 1988], we can find an optimal assignment in cubic time.

Corollary 3.6 The time complexity of sCSP(r ci) is O(n 3 1DI 3 ) , where n is the number of variables.

4 Submodular functions

In this section we will consider a rather more general class of functions, as described in [Topkis, 1978].

Definition 4.1 Let D be a totally ordered set. A function, ¢ : Dk -> E is a submodular function on D if, for all (a1, ... , ak), (b1, ... , bk) E Dk, we have

It is easy to check that all unary functions and all generalized interval functions are submodular. For binary functions, the definition of submodularity can be simplified, as follows .

Remark 4.2 Let D be a totally ordered set. A binary func­ tion, ¢ : D 2 -> E is submodular if and only if, for all u < x, v < y E D, we have:

Example 4.3 Let D be the set {1, 2, . .. , M} with the usual ordering, and consider the binary function 1r M, defined by 7rM(x, y) = M 2 - xy.

Note that, for any u < x, v < y ED, we have: .

Hence, by Remark 4.2, the function 1r M is submodular. D

It follows from Definition 4.1 that the sum of any two sub­ modular functions is submodular. This suggests that in some cases it may be possible to express a submodular function as a sum of simpler sub modular functions. For example, for any unary function 'ljJ : D -> E we have

The main result of this section is Theorem 4.4, which states that any binary submodular function can also be expressed as a sum of generalized interval functions.

Theorem 4.4 Let D be a totally ordered finite set. A binary function, ¢ : D 2 -> E is sub modular if and only if it can be expressed as a sum of generalized interval functions on D.

Proof: By the observations already made, any function ¢ which is equal to a sum of generalized interval functions is clearly submodular.

To establish the converse, we use induction on the tight­ ness of¢, that is, the number of tuples for which the value of ¢ is non-zero. Details are given in [Cohen et al., 2002] . D

Example 4.5 Consider the binary function 1r M on D = {1, 2, . .. , M}, defined in Example 4.3. When M = 3, the values of 1r3 are given by the following table:

Note that:

Hence,

In general, for arbitrary values of M, we have 7rM(x , y) =

We remark that this decomposition is not unique - other de­ compositions exist, including the symmetric decomposition 7rM (x, y) = 1r:W (x , y) + 1r:W(y, x ), where 1r:W (x , y) =

Combining Theorem 4.4 with Corollary 3.6, gives:

Corollary 4.6 For any finite soft constraint language r on a finite totally ordered set D, ijr contains only unary or binary submodular functions, then the time complexity ofsCSP(r) is O(n 3 \D\ 3 ) .

The next result shows that the tractable class identified in Corollary 4.6 is maximal.

Theorem 4. 7 Let r be the set of all binary submodular func­ tions on a totally ordered finite set D, with \D\ ;::: 2.

For any binary function 'ljJ eJ_ r , sCSP(ru{ 'ljJ}) is NP-hard.

Proof: The proof is by reduction from sCSP( { ¢xoR}) to sCSP(r U {'¢} ), where ¢xoR is the binary function defined in Example 2.5. It was pointed out in Example 2.5 that sCSP( { ¢xoR}) corresponds to the MAX-SAT problem for the exclusive-or predicate, which is known to be NP­ hard [ Creignou et al., 200 I]. Hence sCSP (r U {'¢}) is also NP-hard. Details of the reduction are given in [Cohen et al., 2002]. D

5 Applications

In this section we give a number of examples to illustrate the wide range of soft constraints which can be shown to be tractable using the results obtained in the previous sections.

Definition 5.1 For any k-ary relation Ron a set D, we define an associated function, ¢R: Dk ---> E, as follows:

By Corollary 4.6, any collection of crisp constraints, where each constraint is specified by a relation R for which ¢ R is unary or binary submodular, can be solved in polynomial time, even when combined with other soft constraints that are also unary or binary submodular.

Example 5.2 The constraint programming language CHIP incorporates a number of constraint solving techniques for arithmetic and other constraints. In particular, it provides a constraint solver for a restricted class of crisp constraints over natural numbers, referred to as basic constraints [van Henten­ ryck et al., 1992]. These basic constraints are of two kinds, which are referred to as "domain constraints" and "arithmetic constraints". The domain constraints described in [van Hen­ tenryck et a!., 1992] are unary constraints which restrict the value of a variable to some specified finite subset of the nat­ ural numbers. The arithmetic constraints described in [van Hentenryck eta/., 1992] have one of the following forms:

where variables are represented by upper-case letters, and constants by lower case letters, all constants are non-negative real numbers and a is non-zero.

For each of these crisp constraints the associated func­ tion given by Definition 5.1 is unary or binary submodular, hence, by Corollary 3.6, any problem involving constraints of this form can be solved in cubic time. Moreover, any other soft constraints with unary or binary submodular evaluation functions can be added to such problems without sacrificing tractability (including the examples below). D

Now assume, for simplicity, that D = {1, 2, . . . , M}.

Example 5.3 Consider the binary linear function >. defined by >.(x, y) =ax+ by+ c, where a, bE JR+.

This function is submodular and hence, by Corollary 3.6, any collection of such binary linear soft constraints over the discrete set D can be solved in polynomial time. D

Example 5.4 The Euclidean length function J x 2 + y 2 is submodular, and can be used to express the constraint that a 2-dimensional point (x, y) is "as close to the origin as pos­ ~~- D

Example 5.5 The following functions are all submodular:

• 8r(x, y) = lx - Yl r , where r E JR, r ~ 1. The function 8r can be used to express the constraint that: "The values assigned to the variables x and y should be as similar as possible".
• 8t(x , y) = (max(x- y, O)t, where r E JR, r ~ 1. The function 8t can be used to express the constraint that: "The value of x is either less than or as near as possible toy".
• 8r?: (x, y) = { oolx- Ylr if x ~ y otherwise

where r E JR, r ~ 1.

The function 8{::- can be used to express the temporal constraint that: "x occurs as soon as possible after y".

D

Example 5.6 Reconsider the optimization problem defined in Example 1.1. Since '1/Ji is unary, and 8r is binary submod­ ular (Example 5.5), this problem can be solved in cubic time, using the methods developed in this paper.

Let P be the instance with n = 3 and r = 2. The values of 82 are given by the following table:

Hence,

Using this decomposition for 82 , we can construct the graph Gp corresponding to the instance P, as follows.

i\

The minimum weight of any cut in this graph is 1 4 1 , and hence the optimal evaluation of any assignment for P is ¥.

One of the several possible cuts with this weight is indi­ cated by the gray line across the graph, which corresponds to the solution v 1 = 1, v2 = 1, v3 = 2, v4 = 2, vs = 3, v6 = 3. D