Increasing Functional Constraints Need to Be Checked Only Once

1. Introduction

The key technique in solving CSPs is consistency check. Arc consistency algorithms that work on a network ~epresentation of binary CSPs are perhaps the most Important class of consistency algorithms. In this paper, we are also concerned with · arc consistency of binary constraints, in particular, increasing functional constraints.

Over the past two decades, a number of general arc consistency algorithms have been proposed, e.g., AC-3 [Mackworth, 1977], AC-4 [Mohr alld Henderson, 1986], AC-5 [Hentenryck et al., 1992] and AC-6 [Bessiere and Cor~ier, 1993]. Apart from the general algorithms, many specific methods were also designed which are specializations of the general ones for specific constraints [Lauriere, 1978; Mohr and Masini, 1988, Hentenryck et al., 1992]. These methods typically exploit the semantics of individual constraints, and are more efficient in checking these constraints. For instance, in [Hentenryck et al., 1992], AC-5 is specialized for functional, anti-functional and monotonic constraints, and their piecewise generalizations (see their formal definitions in [Hentenryck eta/., 1992]).

Recent years, the CSP model has been implemented in constraint programming languages, such as CHIP [Hentenryck, 1989], Charme [Charme, 1990], Ilog Solver [IIog, 1993], etc., for solving practical combinatorial problems, such as scheduling, sequencing and resource allocations [Dincbas et al., 1990; Hentenryck, 1989]. The basic constraints used in these languages are special cases of functional, anti-functional and monotonic constraints.

In this paper, we propose a more efficient consistency technique for a frequently used subclass of functional constraints, namely, increasing functional constraints (IFC). This technique allows this subclass of constraints (almost all of them) to be checked (or considered) only once in an arc consistency check process.

In a normal process, a constraint needs to be checked many times to maintain consistency. Recheck is necessary when its previously established consistency is broken by other constraints. In the new method, IFCs only need to be checked once. This is achieved by merging the domains of the two variables in a IFC in the initial check such that rechecks will not be necessary. This technique may be embedded in any general arc consistency algorithm. This paper only presents a modified AC-5 algorithm, called AC5+, to incorporate this technique.

Experimental results have shown the new technique outperforms the existing techniques substantially. This saving is important in practice because from our experiences in using two constraint languages, Charme and Ilog Solver to build practical systems, many constraints are IFCs, in particular, equations of the form aX = bY + c, where X and Y are variables, and a and b are positive constants and c a constant.

Section 2 gives defmitions and conventions. Section 3 describes AC-5+. Section 4 presents the new method for IFCs. Section 5 shows the test results. Section 6 discusses the related work and Section 7 concludes the paper.

2. Preliminaries

A binary CSP is defined as follows: ( 1) variables - a finite set of n variables { 1, 2, ... , n}, and (2) domains - each variable i takes its values from an associated finite domain D;. and (3) constraints - a set of binary constrairits C between variables. If i and j are variables (i < J), we assume, for simplicity, that there is at most one constraint rel~ting them, denoted Cij: A solution to a CSP is an assignment of values to vanables such that constraints are satisfied.

A graph G can be associated with a binary CSP, where each node represents a variable i, and each edge between two variables i and j, a constraint, which is expressed as two directed arcs, (i, J) and (j, i). We denote by e the number of arcs in G, by d the size of the largest domain, and by arc( G) the set of arcs in G.

We recall the standard definitions of arc consistency for an arc and a graph.

Definition 1. An arc (i, J) E arc( G) is arc consistent with respect to Di and Dj iff for all v E Di, there exists wE Dj such that Cij(v, w) holds.

Definition 2. A CSP is arc consistent iff for all (i, J) E arc(G) such that (i, J) is arc consistent with respect to Di andDj-

Our new technique requires a total ordering on the variable domain. This total ordering is defmed as follows:

De fin it ion 3. A domain D i = { v J. ... , v a} is totally ordered iff vk< vk+1·

We now defme a functional constraint and an increasing functional constraint.

Definition 4. Given two variables i and j, we denote i ~ j iff for all v E D ~ the~ exists at most one w E Dj such that Ci/v, w). If It exists, then w = fij(v).

A constraint is functional iff i ~ j and j ~ i.

Definition 5. Given two variables, we denote i i j iff (I) i ~ j, and (2) for all u, v E Di such that both fi/u) and f;/v) exist in Dj then u < v impliesf;/u) <f;/v).

Observe that if i i j (or equivalently j i i) then the constraint C ij must be functional , and we call such a constraint increasing functional constraint (IFC). An example of an IFC is X= Y + 5. '

Most earlier algorithms (e.g., AC-3 [Mackworth, 1977], AC-4 [Mohr and Henderson, 1986] and also AC-6 [Bessiere and Cordier, 1993]) do not use the semantics of constraints to achieve better efficiency. AC-5 [Hentenryck eta/. , 1992] is different as the implementations of its two procedures AR.cCoNs and LocALARcCoNs are left open. This means that for different constraints different algorithms could be used. AR.cCoNs checks an arc when it is first encountered, while LocALARcCoNs rechecks it if its consistency is broken by consistency check of other arcs. [Hentenryck et a/., 1992] provides the special AR.cCoNs and LocALARcCoNs procedures for checking functional, anti-functional and monotonic constraints in O(ed).

In this paper, we call these two procedures the initial check procedure and the recheck procedure respectively for intuitive reasons. This separation is important because the algorithm for recheck for certain constraints (e.g., functional constraints) may be different from its initial check algorithm.

In most situations, rechecks take a considerable amount of computation. In this paper, we will try to eliminate the rechecks for IFCs.

3. AC-5+ Algorithm

Before discussing the new technique for IFCs, we first present AC-5+, which provides the data structures and the framework for the discussion of our technique. The intention here is not to propose a new algorithm, but to do minimum modifications to AC-5 so that the new technique can be embedded in it. The main modification is in the domain data structures. In fact, we also modified AC-3 for our technique, which is much easier to modify than AC-5. Due to the space limitation, it is not discussed here.

AC-5+ works with the domain data structures in Figure 1. Like AC-5, we assume a total ordering on the domain.

LetS= {VJ. ... , val with vk < vk+1 be the original domain of i; Di = {vp 1 , ... , vPm} ~S withpk<Pk+1 andm>O Syntax Di.merge: boolean Di.e/ement: set of pairs (v, foe) with v E Sand /oc is a structure, organized as a hash table on key v. Di.values: array [l..a] of elements E S Di.info: an info structure Semantics Di.merge = true if this domain has been merged with another domain =false otherwise /oc.index(Di.e/ement(v)) = p (with v = vp), if v E Di = 0, otherwise Di.values[p] = vp D;.info points to an info structure (see below) (A). Domain data structure Syntax /oc.index: integer Semantics /oc.index = p E {0, ... ,a} (B). /oc data structure Syntax info.size: integer info.min: integer E { 1, ... ,a} info.max: integer E { 1, ... , a} info.succ: array [l..a] of integers E { 1, ... , a} info.pred: array [l..a] of integers E { 1, ... , a} info.arcs: a set of arcs. Semantics info.size = m info.min = p 1 info.max = Pm info.succ[pk] = Pk+ 1 (1 :5: k < m), info.succ[pm1 = + oo info.pred[pk+11 = Pk (1 :5: k < m), info.pred[p 11 =- oo info.arcs = { (k, i) I (k, i) E arc( G), (k, i) is not a IFC} (C). info data structure

Figure 1(A) shows the top level structure. The field merge tells whether this domain has merged with another domain. Its meaning will become clear later. The field element is a set of pairs (v, loc) organized as a hash table on key v, where v E S, and /oc is a structure (Figure l(B)) with its field index holding the array index of v in Di.values (when a value is not even in the original Di, D;.element(v) will return 0). This is different from that in AC-5, where v directly points to the index rather than a structure loc that indirectly points to the same index. This change is important for the new technique for IFCs. The info field gives all the information about the current domain. Its data structure is shown in Figure l(C). This is also different from AC-5 as AC-5 keeps all the infonnation in the domain data structure in Figure l(A). This modification is also crucial to our new technique.

Regarding the info structure, the field size gives the domain size; the fields min and max are used to access the minimum and maximum values in the domain; the fields pred and succ allow accessing in constant time the successor and predecessor of a value in the domain. This representation allows the algorithm to reason about array indices rather than values. These fields are the same as those in AC-5. The extra field is arcs storing the arcs (which are kept elsewhere in AC-5) related to the variable except those IFC arcs because our new technique checks them only once. Then, there is no need to store them.

We now present AC-5+ (Figure 2). It has two parts, the initial check part (line 2 and 3), and the recheck part (line 4-8). Note that in line 2, we use arc(G') instead of arc(G) as in AC-5. arc(G') is the same as arc(G) except that each IFC is expressed as one arc, either (i, j) or (j, i), rather than two arcs. The reason for this will be clear later. Q in AC-5+ has elements of the form <(i, J), W> (line 6), where (i, J) is an arc and w is the array index of a real value (in Dj-values) removed from Dj- Only in one special case, w is the real value itself (see next section). In AC-5, w is always a real value removed from Dj- This change is also important.

Algorithm Ac-5+ begin 1 Q := { }; 2 for each (i,J) E arc(G') do 3 initiaiCheck(i,j, Q) 4 while Q not empty do 5 begin 6 delete <(i,J), W> from Q; 7 recheck(i,j, w, Q) 8 end end

The implementations of the two procedures initialCheck and recheck are left open. Their general defmitions are almost the same as those for ARcCoNs and LocALARcCoNs in AC-5. Due to the space limitation, we will not describe them here. The major difference is that AC-5+ embeds two procedures remove and enqueue inside initialCheck and recheck as it gives more flexibility in implementing specialized initia/Check and recheck procedures. In AC-5, these procedures are in the main AC5 algorithm. remove removes those inconsistent domain values from D i· and enqueue adds elements of the form <(k, i), W> to Q, where (k, i) is a related arc of i and w is either the D;.values array index of a real value or a real value.

AC-5+ inherits all the properties and complexity results of AC-5 as the key operations ·and data structures of them are almost the same. The differences are non-essential.

4. Merge Variable Domains in a IFC

We now describe the proposed technique that checks (almost all) IFC only once. The main idea is to exploit the fact that consistent values in the variable domains of a IFC is one-to-one correspondent and in an increasing order. In initial check, we can make the two variables of a IFC share some key information. Then, later on, domain change of one variable will be felt automatically by the other. In this way, rechecks of the constraint can be avoided.

As indicated, our technique does not guarantee that every IFC will be checked once. Let us describe the condition under which every IFC needs only one check. Take note that every IFC in arc( G) is expressed as one arc (or edge).

Condition: each IFC in arc( G) to be checked (in the initial check process) must have no more than one variable that has appeared in a previously checked IFC (also in the initial check process).

For example, we have IFC arcs (1, 2), (3, 4), and (2, 3). If they are checked in this order, the above condition is not satisfied. It may be rearranged as (1, 2), (2, 3), and (3, 4) to satisfy the above condition.

In practical problem solving, this condition may not re fully satisfied but only partially because the sequencing of constraints may depend on the problem, and the IFCs may also form cycles. In these cases, those IFCs that do not met the condition still need recheck. However, from our experience in building practical systems, there are normally many clusters of IFCs in a practical CSP, and each cluster typically has only 2 to 3 variables. Then, the above condition is always satisfied. That is why we say almost all IFCs need no recheck in our method.

Figure 3 shows the procedure initia/Check for IFCs. Two sub-procedures are used. The first one is mergeCheck (Figure 4), which is used when the arc (i, J) satisfies the above condition. The second one is nonMergeCheck (Figure 6), which is used when the arc (i, J) does not satisfy the condition. These two procedures use enqueue (Figure 5) mentioned in the last section.

Procedure initiaiCheck(in i,j, out Q) begin 1 if not Dimerge then 2 mergeCheck(i,j, Q) 3 elseif D;.merge then 4 nonMergeCheck(i,j, Q) 5 else mergeCheck(j, i, Q) end

mergeCheck merges D; and Dj by making them share the same info and some information in their element fields. Notice that a domain can be merged with any number of other domains. Let us have an example of this merging. Suppose we have the variables X and Y. X has the domain { I 2 4 6 7 9} and Y has the domain { 5 8 9 10 11 12 13}. The IFC is Y =X+ 1. The initial domains for X andY are as follows (only two fields are shown):

Dx.values = 1 2 4 6 7 9 loc.index(Dx.element(v)) = 1 2 3 4 5 6 Dy.values = 5 8 9 10 11 12 l3 loc.index(Dy.element(w)) = 1 2 3 4 5 6 7 After initial check, the domains become: Dx.values = 1 2 4 6 7 9 loc.index(Dx.element(v)) = 0 0 3 0 5 6 Dy.values = u u 5 u 8 10 loc.index(Dy.elementlfxy(v)))= 3 5 6

Note that u stands for undefmed, and consistent values in the new Dj-values are still in the original order. Mter initial check, for each pair of matching values v E Dx and fxy(v) E Dr Dx.element(v) and Dy.elementifxy(v)) have the same Zoe. For those values in the initial Dy but not in the new Dy, their loc.index all have 0.

procedure enqueue(in i, A, inout Q} Q f- Q u {<arc, w>) I arc E D;.info.arcs, WE A}.

Figure 5. Procedure for adding elements to Q for recheck Here are the key points to show the correctness of mergeCheck.

• The array newValues created with the same size as D;.values is used to store D;'s corresponding values in D ·. Because IFCs are functional, the number of values in Dj after the initial check cannot be more than the size of tHe array in D;.values. In line 8, whenever a value v E D; has a corresponding value w E Dj, w is stored in newValues in the index;th cell. indexj (rme 7) is obtained when testing the membership of f;j(v) in Dj using the hash table in Dielement. Thus, after line tO, newValues has all the consistent values in D· with regard to D;. Consistent values in D; and new~alues also have the same array indices. Due to the i t j property. values in newValues are still totally ordered.

Line 10 deletes. those vatu~ .in Di with matchi~g values in D; wtthout modifymg Dj-element. Thts operation can be done in Disucc whicli is subsequently replaced in line 23. So, deleting those matching values in Dj does no harm. Line 13-t7 removes those values in Dj tliat do not have matching values in D; by updating only Dfs hash table. Other information on Dj requires no ujxlating as it is subsequently replaced (line 23).

In line 22, the original Di.values is replaced with newVa/ues. It is clear no conststent value is lost and no inconsistent value is kept in the new D1.va/ues. All the inconsistent values in D; are removed in line 5.

• Line 9 makes Dielementifij(v)) points to the same /oc as D;.element(v) (as v E D; andf;/v) E Dj are consistent). This ensures that when a value x is de feted from D; (or Dj) by setting loc.index(D;.element(x)) (or loc.index(Dj-element(x)) to 0 in the later process, the correspondmg value in Dj (or D;) is also deleted.

Line 21 concatenates ihe related arcs of i and j and assign it to D;.info.arcs. This and the operation in line 23 ensure that when D; (or Dj) is modified later (after initial check), related arcs of both i and j are activated for recheck.

Line 23 makes Dj share the same info with D;. It is clear that according to the definition of IFC, all the information in D;.info and Dj.info should be the same after the initial check. The merging of domains is complete. Later on, anything happens to D; (or Dj), Dj (or D;) feels it automatically. .

• The use of indices in At is crucial. When some values are removed from D; (or Dj) later on, the corresponding values in those domains merged with D; (or D) are also removed due to our merging operations. lndtces in A 1 reflects all these removals. Real domain values carmot be used in A 1 because they only reflect the value changes in D i but not the others merged with it.

However, A2 does contain the actual values removed from D· (the only case in AC-5+) ~cau.se !Jival~es is replac~ with newValues so that usmg mdtces wtll be incorrect. As Dj does not have any variable merged with it, real values can be used. Note that for a real value, we use { w} as an indicator (line 15) (in a real implementation another indicator may be used). Procedure recheck uses this indicator to identify the value type, an array index or a real domain value.

nonMergeCheck is given in Figure 6. Its correctness is clear. It is almost the same as AR.cCoNs in AC-5 for functional constraints except that both arcs (i, J) and (i, i) are checked in nonMergeCheck. Note that in line 13 and 14, two arcs for the constraint are attached to two variables. These two arcs are not there originally, and they may require rechecks as they did not merge.

Since some IFCs may still need recheck, the procedure recheck is given in Figure 7, which is almost the same as that in AC-5 except in line 1, where we need to test whether w is a real domain value or an array index.

Due to the use of hash table, each value in D; needs to be checked only once in mergeCheck and nonMergeCheck. Thus, initia/Check is O(d). recheck is 0(1) as only one value needs to be checked. Hence, algorithm AC-5+ is O(ed) for IFCs, which is the same as for functional constraints in AC-5. However, our algorithm eliminates most of the rechecks needed in AC-5.

initia/Check and recheck methods for non-IFC functional, anti-functional and monotonic constraints can be easily devised for Ac-s+. They are basically the same as those in AC-5.

5. Experimental Results

Here, we first compare the performances of Ac-s+ and AC5 over equations, inequalities and disequations, which are the basic constraints of the current constraint languages. Equations, inequalities and disequations are special cases of functional, monotonic and anti-functional constraints respectively. Increasing equations, such as X = aY + b, where X and Y are variables, a and b are constants and a is positive, are special cases of IFCs.

Since AC-3 may be preferable in practice [Hentenryck et al., 1992] because of its space efficiency, we also compare the performance of our technique with the existing one in the context of AC-3. In particular, we compare two versions of AC-3: AC-3S and AC-3+. AC-3S uses the special handling techniques in [Hentenryck, 1989] (it cannot use those in AC-5 because of the representation limitation of AC-3) for equations, inequalities and disequations. AC-3+ uses our new method for IFCs without changing the techniques for non-IFC equations, inequalities and disequations. All the algorithms are implemented in CMU Common Lisp on SPARC-2.

We report two sets of tests. One set uses CSPs with only IFCs, in particular equations of the type: X= aY + b, where X and Y are variables, a and b are constants and a is also positive. This set of tests is to show the effects of the new technique on IFCs alone. The other set uses typical scheduling problems. Scheduling problems are used here because most applications of constraint programming are in scheduling, sequencing and other similar domains.

For the first set of tests, variables, domains and constraints are randomly generated. The number of variables ranges from 40 to 80, the domain sizes range from 10 to 100, and the number of constraints ranges from 45 to 90. Figure 8 shows the performance comparison of AC-5 and Ac-s+ in percentage terms over 18 problems. The performance of AC-5 is taken as 100% (shown as the dash line). AC-5+ takes only 52% to 80% of the time for AC-5 for arc consistency.

Figure 9 shows the compiuison on the same set of IFC CSPs with AC-3S and AC-3+. The performance of AC-3S is taken as 100%. AC-3+ only uses 42% to 62% of the time taken by AC-3S. From the two figures, we can see that AC3+ improves more than Ac-s+. This is because AC-5 has a more efficient algorithm for functional constraints.

The second set of tests is intended to show what we may see when the new technique is used in real applications. The test problems are typical job scheduling problems. In this domain, we need to schedule a number of jobs 1 = { J I· 12, ... , 1,J, and each job consists of a number of operations 1; = (0Pi1· 0Pi2· ... Op;ml· The operations in each job have to be performed in a fixed sequence. Thus, the start time S ik of one operation must be greater than or equal to the ending time Eik-1 of its previous operation, i.e., S;k ~ Eik-1· Each operation also has a duration Duik· Then, we have the constraint Eik = S;k + Du;k (which is a IFC). Each job has a due time Dt;, by which it must be finished, i.e., Eim ~ Dt;. There are also other constraints such as certain operations from different jobs may need to start at the same time or finished no later than certain time, etc. This by no means describes a full scheduling problem. A real problem also needs to consider resources, and requires a good solution. However, these are more to do with heuristic search strategies rather than consistency check, and they are out of the scope of this work. The results reported here are only for achieving consistency.

For this set of tests, we fix the number of operations to be 5 for each job, which means 10 variables per job. Each domain has 100 values. However, the number of jobs is randomly generated for each problem, ranging from 4 to 8. The constraints are also randomly sequenced. Figure 10 and 11 show the performance comparisons of AC-5 and AC-5+, and AC-3S and AC-3+ respectively (over 18 problems). It can be seen that the new technique produces substantial saving. AC-5+ takes only 55% to 80% of the time for AC-5. AC-3+ takes 42% to 57% of the time for AC-3S. On the surface, it seems that our technique should save less with the second set of tests because other types of constraints are involved. But from the figures, the savings are simmilar. This is because in the frrst set of tests, many IFCs may not be merged due to the condition in Section 4.

The above saving is resulted from only a single arc consistency check. When applying the technique to constraint programming even more saving could be achieved due to backtrack search which requires consistency check to be performed many times.

6. Related Work

Many general and specific arc consistency techniques have been developed in the past. In real applications, specific methods perhaps play a more important role than general ones because of their efficiency. Most commonly used specific consistency methods are for functional, anti­ functional, and monotonic constraints [Hentenryck, 1989; Hentenryck et al. , 1992; Mohr and Masini, 1988]. Their special cases also form the core of the current constraint programming languages, such as CHIP [Hentenryck, 1989], Charme [Charme, 1990], Hog Solver [Hog, 1993], etc.

AC-5 [Hentenryck et a/., 1992] is a generic arc consistency algorithm, i.e., it allows both general and specific checking of constraints. In [Hentenryck et a/., 1992], it is specialized for functional constraints, anti­ functional constraints, monotonic constraints, and their piecewise constraints. The algorithm achieves O(ed) for these constraint classes. Our work is motivated by this algorithm. It is an improvement to AC-5's special technique for functional constraints. Although our technique is still O(ed), experiments have shown it is more efficient than that in AC-5.

Mohr and Masini [Mohr and Masini, 1988] discovered independently that binary equations, inequalities, and disequations can be solved in O(ed). Earlier work on constraint solvers (e.g., ALICE [Lauriere, 1978]) and constraint programming languages (e.g., CHIP [Hentenryck, 1989]) also presented special algorithms for these types of constraints. However, equations in all these methods need to be checked many times.

7. Conclusion

We have proposed a new consistency technique for IFCs. It checks most IFCs only once rather than many times. Although this technique does not reduce the complexity, our experiments have shown it outperforms substantially the existing methods. The main application of this technique will be in constraint programming languages.

Acknowledgments: I would like to thank Kim-Heng Teo, Chee-Kit Looi and anonymous IJCAI reviewers for their helpful comments and suggestions.