Exploiting Interchangeabilities in Constraint-Satisfaction Problems

1 Introduction and Motivation

Constraint Satisfaction is a well-studied research area of recent years. Using constraint satisfaction methods ~any problems - especially in AI - can be represented ~n a very declarative way by identifying the variables of mterest for the problem, laying down the domains for the vari_ables and restricting the variable assignments by constramts. More formally, a constraint network R con­ sists of a finite set V = { v1 , ... , Vn} of variables and a set C = { c1, ... , Ce} of constraints. Associated with each variable v is a finite, discrete domain Dv . A cons­ traint c on the variables VJ: ~ V is in its extensional form a subset of the Cartesian product of the domains of the afflicted variables. The expression var( c) denotes the tuple of variables the constraint is defined on, and rei( c)~ lvevar(c)Dv is the relational information of the constraint c. 1 The assignment of a value d E Dv to a variab_le v is denoted by v+-d. A tuple t of assignments of vanables VJ: ~ V satisfies a constraint c, if and only ift[var(c)] E rel(c). 2

·This work was supported by Siemens Austria AG under project grant CSS (GR 21/96106/4).

1 0ur notation is similar to the one used in [Dechter, 1992].

A_ constraint satisfa~tion problem (CSP) is the task of findmg one or all variable assignments for a constraint network R such that all the constraints of Rare satisfied. There are various techniques (like network consistency t~chniques or. backtrack search procedures) for the hand­ hog and solvmg of constraint networks (good descripti­ ons can be found in [Mackw()rth, 1977; Mackworth, 1987; Haralick and Elliott, 1980; Dechter and Pearl, 1988; Dechter, 1992]). Though, it is well-known that the use of special methods for certain problem types can reduce search effort. In this paper we focus on problems where the domain values are structured objects rather than ato­ mic data, and the constraints refer to attributes of the obje~ts ~nd not to the objects as a whole. Examples of apphcat10~ areas o~ these types of problems are design, configuration, or d1agnosis. Mittal and Frayman [Mit­ tal and Frayman, 1987] have proposed an approach of partial choices, where at each search step a decision is ma?e only for a part (i.e., an attribute) of a constraint vanable. The methods partial commitment and partial guess are essentially least commitment techniques where some underconstrained decisions are delayed until more infor~ation is derived. Another interesting work in this field IS [Mackworth et al., 1985], where an hierarchical arc~consistency procedure (HAC) is introduced. This al­ gonthm proceeds on the assumption that the variable domains are organized hierarchically in subsets, where the leaf nodes of each domain hierarchy are the intrinsic domain elements, whilst the "abstract" nodes represent groups of domain values with common properties. If the con~traints ~r~at groups of domain values equally, HAC avmds repetitive checks by filtering on abstract domain levels.

Thus, for many problem areas it is a matter of fact that some domain objects of a constraint variable be­ have in the same manner and it is therefore a waste of search time to handle them as totally different objects. Freuder introduced in [Freuder, 1991] the notion of in­ terchangeability, where two domain values are interchangeable in some local or global environment, if they can be substituted for each other without any effects to the environment. Let us summarize the two main definiti­ ons.

2 t[A] stands for the projection in the sense of relational algebra and extracts for our purposes exactly those values of

the tuple t which are relevant to the constraint.

DEFINITION 1.1 (FULL INTERCHANGEABILITY [FREU­ DER, 1991]) Two values d1 and d2 of a domain Dv of a constraint network R are fully interchangeable, if and only if {1} every solution to R which contains d1 as an assignment for v remains a solution when d2 is substi­ tuted for d1, and (e) every solution to R which contains d2 as an assignment for v remains a solution when d1 is substituted for d2 .

DEFINITION 1.2 (NEIGHBORHOOD INTERCHANGEABI­ LITY [FREUDER, 1991]) Two values d1 and d2 for a va­ riable v in a constraint network are said to be neighbor­ hood interchangeable, if and only if the following condi­ tion holds (C is the set of all constraints in the network):

Neighborhood interchangeability is a sufficient, but not a necessary condition for full interchangeability.

It is shown in [Freuder, 1991] that all neighborhood interchangeabilities can be computed in a pre-phase of search in 0( n 2 .a 2 ?. Then, all interchangeable values can be replaced by one representative, which is essenti­ ally a form of problem reduction, because a subsequent search has to handle a network of eventually smaller size. It is proven that the usage of local interchangeabilities at preprocessing time is guaranteed to be cost effective for some CSPs.

But it is often the fact that different domain values are interchangeable only w.r.t. certain constraints, whilst there are constraints which distinguish between the int­ rinsic values. In that cases, neighborhood interchange­ ability makes no use of that nuances of equivalence. We extend Freuder's ideas in a strict manner: we try to find groups of domain values which are essentially not distin­ guishable w. r. t. a single constraint. If a domain Dv is filtered by a constraint c, the values of Dv must be enu­ merated and checked against other value constellations. We propose the replacement of Dv by classes of values (a domain partition w.r .t. c), where the size of the new domain and therefore the number of checks are minimal subject to c, without loss of any information.

The paper is organized in the following way: Section 2 gives a formal definition of domain partitions and shows a simple way of computing them by constructing dis­ crimination trees. In Section 3 we show how various algorithms can be modified in term to use these domain classifications, and in Section 4 we evaluate the proposed techniques by experimental results. Section 5 concludes the work.

3 n is the number of variables and a is the maximum do­ main size. The network is assumed to be binary.

2 Domain Partitions

On each domain Dv of a constraint network and each constraint c where v E var(c), an equivalence relation E~ can be defined, where two domain values of Dv are equivalent in regard of E~, if and only if they behave in exactly the same manner w.r.t. the constraint c. The key item is that this equivalence relation induces a partition of a variable domain into groups of locally (i.e., subject to a single constraint) interchangeable values .

DEFINITION 2.1 (THE RELATION E~) Let c be a cons­ traint of a constraint network R and v E var(c). Two values d1 and d2 of the domain Dv are in the relation E~ (we write d1 E~ d2), if and only if the following condition holds:

(Note the difference to neighborhood interchangeability: the relation E~ depends on the single constraint c.)

THEOREM 2.1 The relation E~ is an equivalence rela­ tion.

PROOF SKETCH: Two domain values d1, d2 E Dv are in the relation E~, if the set of all assignment tuples where d1 is assigned to v and the constraint c is satisfied is equivalent to the set where d2 is assigned to v. The­ refore, E~ is ,in fact an equivalence relation, because it is defined by the equality-relation on sets, which is - of course - an equivalence relation. 0

CoROLLARY 2.2 It is well-known in set theory that each equivalence relation on a set S induces a partition of S, which is a set of non-vacuous subsets of S where the elements of the partition are mutual exclusive and the decomposition is exhaustive. Thus, according to each constraint c of a constraint network every domain Dv (v E var(c)) can be partitioned into equivalence classes induced by E~. We write 1r Ev, or 11'~ for short. c

EXAMPLE: Let the variables v1 , v2 and v3 represent three ports of a board where modules must be moun­ ted on. The available modules have two main charac­ teristics: their mode ("analog" or "digital", abbreviated by a resp. d) and their version number (1 or 2). Thus, the domains of the variables can be specified by

The following constraints restrict the possible constel­ lations: (c12) the modules mounted on v1 and v2 must be of different mode; (c13) the modules mounted on v1 and V3 must have different version numbers. From the per­ spective of port v1, the domain Dv 1 can be partitioned in the following way:

Note that in this simple CSP there is no pair of neigh­ borhood or fully interchangeable domain values in Dv 1 in the sense of Definitions 1.1 and 1.2. 0

In that way, every element of a domain partition 71'~ is a set of domain values which are interchangea­ ble w.r.t. the constraint c. Similar to [Freuder, 1991], these domain partitions can be computed by generating discrimination trees. A discrimination tree is a tuple (N,E,tP,t/J), where N is a set of nodes, Eisa set of edges (each edge is a pair (nl, n2), nl, n2 E N), tP is a labeling function which assigns to each node of N a (possible empty) set of domain values, and t/J is a labe­ ling function which assigns to each edge from E a tuple of domain values.

We postulate a procedure DT(c, v) for computing a discrimination tree for the domain of a variable v w.r.t. the constraint c (v E var(c)). Basically, the following is done by DT( c, v ): for each value d of the domain Dv starting at the root a branch is generated, where the la­ bels t/J of the edges of this branch are the corresponding consistent tuples t', where t E rel(c) such that t[v) = d and t' = t[var(c) - v]. If existing suitable parts of the branch are constructed already, they will be used. If all consistent tuples of the variable v are on the branch, the actual domain value is added to the node label tP of the current node. A canonical ordering of the domain values is assumed. Therefore, the set of non-vacuous node labels of a discrimination tree produced by a proce­ dure call DT( c, v) is a domain partition 11'~ as described previously. 4

An upper bound of the complexity of procedure DT(c, v) is O(ak) where a is the domain size of v and k is the arity of c. This can be proven by the follo­ wing considerations: the outer loop (expand a branch for each domain value) is performed a times, and the maximal number of suitable tuples t' is the number of different ~k - !)-tuples of domain elements, which is at most ak- . Thus, a worst-case upper bound of the pro­ cedure DT(c, v) is O(a.ak-l) = O(ak). If for every cons­ traint every domain of the corresponding variables is de­ composed by building a discrimination tree, the upper bound complexity is O(e.k.at), where e is the number of constraints and all constraints are at most of arity k. Therefore, an effort of this magnitude must' be spent for the computation of all domain partitions in a preproces­ sing phase of search.

3 Adaptation of Various Constraint Propagation Algorithms

Now we are in the position to show how these domain partitions can be used to increase efficiency of various existing algorithms. We give a few modifications of the key procedures and show the advantages of the use of such interchangeability-techniques for certain problem types. We focus on binary CSPs.

3.1 Constraint Filtering

Constraints are most commonly used in a destructive manner. The critical and most time consuming task in network consistency procedures is to check if all values of a particular variable domain can potentially be member of a solution. These checks are done repetitively for sin­ gular variables w.r .t . singular constraints. In the case of binary constraints, usually the procedure revise(vi, v;) is used, which removes all values of Dv; for which no value of the domain of v; can be found such that the binary constraint Cij between Vi and v; is satisfied. Thus, the worst-case complexity of revise is O(a 2 ) where a is the maximum domain size.

· A detailed description of the procedure DT and a proof that it actually computes the right thing is given in an ex­ tended report version of this paper.

In Figure 1, a modified procedure called revised" is depicted. We use the expression~ (dis a domain value) to denote the equivalence class of value d subject to the equivalence relationE~: ~ = {d' E Dv I dE~d'} .

1 2 3 4 5 6 7 8 9 10 11 12 13 procedure revised" (vi, v; ) : .6.i := {}; do until Dv; becomes empty: z := an element of Dv;; .6.; := Dv;; do until .6.; becomes empty: y := an element of .6.;; if (z, y) E rel(ci;) then .6.i := .6.i U (~:; n Dv; ); .6.; := {}; tJ · else .6.; := .6.; - 'iic:;; Dv := Dv -~; .. , . . ...... , Dv; := .6.i ·

The main difference between the "classical" revise and revised" is that the former checks in the worst case all tuples from Dv; x Dv; and the latter treats groups of in­ terchangeable values equally and therefore possibly saves checks utilizing information included in the domain par­ titions. If we assume that the domain partitions (i.e., the sets 11'~ for all constraints c and all variables v E var(c)) are of size al (1 ~ al ~ a), a worst case bound of algo­ rithm revised" is O(a1 2 ). We see that if the structure of a constraint network gets no use of domain partitions (all domain partitions 1r are of same size as their cor­ responding domains), al would be equal to a and the worst case behavior is not worse than that of the stan­ dard revise algorithm. Of course, the smaller al is in comparison to a, the better is the improvement.

It is easy to see that revise and revised" produce exactly the same outcome. In that way, algorithms which use revise (such as arc- and path-consistency al­ gorithms) simply have to change each call to revise by a call to revised" and get effective use of reduced do­ main sizes. Also many backtrack procedures use revise and therefore can benefit from revised". The palette ranges from classical chronological backtracking, where at each search step the domain of the current variable is made consistent to all past assignments, to various forms of look-ahead schemes, where the future search space is brought to certain degrees of (arc-)consistency. Particu­ larly at the latter approaches, revise is used excessively.

3.2 Backtrack Search

In the following, we want to evolve a slightly modified tree search scheme where interchangeable search bran­ ches are recognized by the use of domain partition information. The structure of the algorithm is basically the same as classical backtrack tree search as described, for instance, in [Fox and Nadel, 1989].

But first we have to give some notations we need for the development of the search procedure. Each output of a traditional backtrack procedure is an assignment tuple representing a solution for the given CSP. Because we want to handle groups of interchangeable values, we have to modify the form of the output. Instead of single assignment values, sets are used. In that way, assignment tuples are shifted to assignment bundles.

DEFINITION 3.1 (ASSIGNMENT BUNDLE) Let V be the set of n variables of a constmint network R. An n-tuple .£l where the ith element of .£l {1 $ i $ n} is a non­ vacuous subset of the domain Dv; is called an assignment bundle.

DEFINITION 3.2 (SOLUTION BUNDLE) LetT be the set of all solutions to a given constraint network R. An assignment bundle a = {at, ... , an} on the variables V of R is said to be a solution bundle, if and only if .o!lt X · ·· X an ~ T.

Therefore, solution bundles represent groups of path' through the search tree, where each path stands for a valid variable assignment of the constraint network. The terms of local and global consistency (see, for instance, [Dechter, 1992]) can be extended to assignment bundles.

DEFINITION 3.3 (CONSISTENCY OF ASSIGNMENT BUNDLES)

• An assignment bundle aP on the variables Vp ~ V is said to be locally consistent, if every assignment tuple extractable from aP is locallyf consistent.
• An assignment bundle .£lP on the variables V, ~ V is said to be globally consistent, if there exists an extension assignment bundle aJ on the variables (V- V,) such that aP U a/ is a solution bundle.
• An assignment bundle aP is said to be inconsistent, if every assignment tuple extractable from .£lP is in­ consistent (i.e., no tuple can be extended to a solu­ tion).

Now we want to modify the classical backtrack search shell such that for each pass a bundle of assignments is computed. The following theorem gives us the funda­ mental basis for the utilization of domain partitions for that purposes.

THEOREM 3.1 Let .£lP be an assignment bundle on the variables Vp C V which is either globally consistent or inconsistent . . Let v be a variable of V - V, and 6" be a subset of (or equal to) the domain Dv such that the following two conditions hold:

1. (Cf are all binary constmints from v to variables of

1. .£lP + 6" is locally consistent; v- V,) Vdt,d2 E 6": Vc E Cl: dtE~d2·

Then .£lP +6" is either globally consistent or inconsistent.

~I.e., all the constraints of the subnetwork defined by the variables Vp are satisfied.

PROOF SKETCH: (I) If .£lP is inconsistent, then there is no way to extend it to a solution and therefore .£lP + 6" is also inconsistent. (II) Suppose .£lP is globally consistent and .£lP + 6" is neither globally consistent nor inconsi­ stent. Then two assignment tuples it and t2 have to exist, where it, t2 E 16e.o.·+6. 6 and one of them (say tt) is globally consistent (an extension to a solution is guaranteed) and the other (t2) is not globally consistent. This can not be the case, because the assignment values of v in it and t2 are interchangeable both w.r.t. the past (by the maintenance of local consistency) and w.r.t. all constraints to future variables. 0

1 procedure backtrackinffP(k,D): 2 revisedp {k,p} for 1 $ p < k; 3 % or do some kind of look ahead filtering 4 dk- D[k]; 5 do until dk becomes empty: 6 choose x from dk; 7 Cl - all constraints on vk to future vars,· 8 D[k]- <ncec' ~~) n dk; 9 dk - dk- D[k]; 10 if k = n 11 then output(D ); 12 else backtmckinffP (k + 1,D ).

Now the modification of the backtmck procedure is easy. Figure 2 sketches the new algorithm backtrackingdp. At each cycle in the search process the set of variables can be partitioned into three groups: the past variables, the current variable, and the future varia­ bles. Since all the remaining domain values of the cur­ rent variable are consistent to the assignments of the past variables (this is guaranteed by the revise at line 2), they are interchangeable w.r.t. that partial solution (bundle) . Now the domain of the current variable is going to be partitioned along their constraints to future variables. For each group of such interchangeable values a new search branch is opened. Clearly, each output of a call to that procedure is an assignment bundle. The follo­ wing theorem states soundness and completeness of the proposed algorithm.

THEOREM 3.2 Let D be the set of all variable domains of a constmint network R. Each output a of a procedure call backtrackingdP(1, D) is a solution bundle toR. The set of all outputs cover all solutions.

PROOF SKETCH: The design of the algorithm is gui­ ded by Theorem 3.1. Thus, at each cycle of the search process the derived assignment bundle is either globally consistent or inconsistent. Inconsistency leads to a dead­ end, each output is globally consistent.

The algorithm passes through the whole search tree (even if interchangeable subtrees are condensed) and the­ refore computes all solutions. 0

The advantageous behavior of the search shell backtrackingdp for certain problem types is obvious. In­ terchangeable search branches are bundled and visited once. If a dead-end occurs, all the partial assignments represented by the derived assignment bundle are proven to be conflicting. A solution bundle represents a group of valid assignments.

So we conclude, if the described domain partition knowledge is available, it can be used in a wide range of CSP algorithms (both at filtering and search) with mini­ mal change of procedures. Apart from a small amount of additional overhead of computing domain partitions in a preprocessing phase and managing groups of domain values instead of singular elements, the new worst-case complexities are not worse than that of the original algo­ rithms. If the problem structures are adequate for (i.e., if the cardinality of domain decompositions are really smaller than the original domain sizes), effective cost re­ ductions can be achieved.

4 Performance Analysis by Experiments

Now we want to investigate the indicated performance improvements of our augmented search technique by ex­ perimental analysis. To identify those areas of CSPs in­ terchangeability makes most capital out of, we are going to use the same test model as proposed in [Benson and Freuder, 1992].

4.1 The Experimental Model

Different types of problems can be characterized by the following four parameters: (1) n, the number of cons­ traint variables. (2) a, the maximum domain size. (3) t, the constraint tightness. The tightness of a constraint is the fraction of the number of forbidden tuples to the number of all possible tuples, and ranges therefore bet­ ween 0 and 1. The higher t grows, the more value tuples are ruled out by the constraint (constraints with high values oft are said to be tight). (4) d, the constraint density. This is an indicator of how many constraints are defined in the network and therefore, how dense the constraint network is. d is a value between 0 and 1 and is specified as follows: Let n be the number of variables, e the number of constraints; the maximum number of constraints emax is n .(n 2 -l), the minimum emin is n- 1 (a connected constraint graph is assumed); then dis the value e-em;a . . In that way, the higher d is, the more ema.z:-em'" constraints are in the network.

Different algorithms are run on randomly generated CSPs and the results are compared. The tests are re­ stricted to binary CSPs.

4.2 Test Cases and Results

Our CSP generator produces samples of random CSPs, where the four parameters n, a, t and d ranges on adju­ sted intervals. In [Benson and Freuder, 1992] it was poin­ ted out that interchangeability techniques are most pro­ fitable if (1) the problem space grows (nand a grow), (2) the constraint tightness is small, and (3) the constraint density is small. The combination of the last two points specifies those regions of problems where the CSPs are under-constrained. These are problems with many solu­ tions.

We tested our algorithms in that manner and came to similar results. Furthermore, our analysis shows that the use of domain partitions w.r.t . single constraints beats neighborhood interchangeability in all the test ca­ ses. This should be demonstrated by the subsequent results.

In the following, three forward-checkin/ search pro­ cedures are compared. The first is classical forward­ checking {FC). The second is forward-checking where all neighborhood interchangeable domain values are re­ placed by one representative value in the preface of search {FC-NI) . The third is an instance of the search scheme backtrackingdp (see Figure 2) where forward­ checking filtering is used. We call it FC-DP. A good indicator of the complexity of the search process is the number of consistency checks. Of course, the checks nee­ ded for the computation of neighborhood interchange­ ability resp. the domain partitions are added to the run­ time checks. The sample of each test are 50 randomly generated CSPs.

The first test demonstrates that utilization of inter­ changeability grows if the problem increases. The varia­ ble size n steps from 6 to 10, the maximum domain size a is fixed on 5, and the constraint tightness t and density d are from the interval [0.1- 0.4] (the profitable ranges for the use of interchangeability!).

Figure 3 shows the results. It can be seen that the positive effect of FC-NI and FC-DP grows with the size of n. Furthermore, our algorithm FC-DP is clearly bet­ ter than FC-NI, and the distance increases with n.

The second and third test holds n = 10, d = 5, and steps t (resp. d) from 0.1 to 0.9, d (resp. t) is randomly chosen from interval [0.1- 0.3] . As depicted in Figure 4 and Figure 5, FC-NI and FC-DP are superior to classical FC when t (resp. d) is small. It can also be seen that FC-DP definitely beats FC-NI at these problem types.

These results are convincing. The more tuples are permitted by a constraint (the smaller t is), the better is the chance that different variable values behave in the same manner w.r.t. the constraint and therefore came into the same class of domain -values. If the constraint net is not dense (there are few constraints), there are at each choice point for a variable assignment few future constraints and the interchangeable groups of values are going to split less (line 8 of the backtrackingdP algo­ rithm, depicted in Figure 2).

6 Forward-checking is a backtrack procedure where at each cycle in the search process all the future variables are filtered against the last-assigned variable. This method is known to behave in a very efficient manner [Haralick and Elliott, 1980].

The lack of FC-NI is that it uses only the informa­ tion that domain values are interchangeable w.r.t . all the connected constraints. In that sense, FC-DP is more accurate because of greater degree of granularity. And this can be achieved with the same overhead as the com­ putation of all neighborhood interchangeabilities.

5 Conclusion

We have developed a formal basis for extraction and re­ presentation of interchangeable domain values in cons­ traint satisfaction problems. The bulk of existing cons­ traint satisfaction algorithms can be adapted to ex­ ploit this information. Application fields arise in many areas of model-based reasoning (such as configurotion, simulation or diagnosis), mainly in those cases where component-oriented systems are modelled in terms of constraint problems. Thereby, identifying the variables for a CSP, possible values for the variables are most of­ ten representations of complex real-world objects rather than unstructured constants. These objects (consider components) are described by various features. Along these features objects can be grouped into classes where the elements of each class have some set of common pro­ perties. In that way, constraints are specifying relati­ ons on different aspects of the system and take classes of components rather than singular values into conside­ ration. If that is noticed at reasoning, a much more adequate inference technique is employed.

Acknowledgments

I am very grateful to Markus Stumptner and Thomas Havelka for valuable discussions and comments on an earlier version of this paper.