An Efficient Arc Consistency Algorithm for a Class of CSP Problems
Proceedings of the Twelfth International Joint Conference on Artificial Intelligence. Automated Reasoning. Pages 325-329.
© 1991 International Joint Conferences on Artificial Intelligence
Abstract
Consistency Techniques have been studied extensively in the past as a way of tackling Constraint Satisfaction Problems (CSP). In particular various arc consistency algorithms have been proposed, originating from Waltz's filtering algorithm [20] and culminating in the optimal algorithm AC-4 of Mohr and Henderson [13]. AC-4 runs in O(ed 2 ) in the worst case where e is the number of arcs (or constraints) and d is the size of the largest domain. Being applicable to the whole class of (binary) CSP, these algorithms do not take into account the semantics of constraints. In this paper, we present a new generic arc consistency algorithm AC-5. The algorithm is parametrized on two specified procedures and can be instantiated to reduce to AC-3 and AC4. More important, AC-5 can be instantiated to produce an 0(ed) algorithm for two important classes of constraints: functional and monotonic constraints. We et.lso show that AC-5 has an important application in Constraint Logic Programming over Finite Domains [18]. The kernel of the constraint-solver for such a programming language is an arc consistency algorithm for a set of basic constraints. We prove that AC-5, in conjunction with node consistency, provides a decision procedure for these constraints running in time O(ed).
- R. Decbter and J. Pearl. Network-baaed heuristics for constraint satisfaction problema. Artificial Intelligence, 34:1-38, 1988.
- M . Dincbaa, H. Simonis, and P. Van Hentenryck. Solving Lar11e Combinatorial Problema in Logic Programming. Journal of Log•c Programming, S(l-:1):75-93, 1990.
- M. Dincbaa and al. The Constraint Logic Programming Language CHIP. In FGCS-88, Tokyo, 1988.
- E.C. Freuder. Syntheai•ing Constraint Expressions. CACM, :11:958-966, 1978.
- J. Gaachnig. A Constraint Satisfaction Method for Inference Mak- ing. In Annual Conf. on Circuit S111tem Theof11, 1974.
- R.M. Haralick and G.L. Elliot. Increasing Tree Search Effi- ciency for Constraint Satisfaction Problema. Artificial Intelli- gence, 14:~63-313, 1980.
- J. Jaffar and S. MichayloY. Methodology and Implementation of a CLP System. In ICLP-87, Melbourne 1987.
- S. Kaaif. On the Parallel Complexity of Discrete Relaxation in Constraint Satisfaction Networks. AI Journa~ 45:~75-~86, 1990.
- J-L. Lauriere. A Language and a Program for Statin' and SolYing Combinatorial Problema. Artificial Intelligence, lOp), 1978.
- A.K. Mack worth. Consistency in Networks of Relations. AI Jour- na~ 8{1):99-118, 1977.
- A.K. Mackworth. Con1traint Sati•faction, Yolume Encyclopedia of Artificial Intelligence. Wiley, 1987. [1:1)
- A.K. Mackworth and E. C. Freuder. The Complexity of some Poly- nomial Network Consistency Algorithms for Constraint Satisfac- tion Problema. Artificial Intelligence, ~5:65-74, 1985.
- R. Mohr and T .C. Henderson. Arc and Path Consistency ReYis- ited. Artificial Intelligence, :18 : ~~5-~33, 1986.
- U . Montanari. Networks of Constraints: Fundamental Properties and Applications to Picture Processing. Information Science, 7(~) : 95-13:1, 1974.
- Montanari, U and Rossi, F. Constraint Relaxation May Be Perfect In To Appear in Artificial Intelligence.
- B. Nadel. Constraint Satisfaction Algorithms . Computational Intelligence, 5( 4):~88-~~4, 1989.
- P. Van Hentenryck. A Framework for Consistency Techniques in Logic Programming. In IJCAI-87, Milan, 1987.
- P. Van Hentenryck. Con1traint Sati•faction in Logic Program- ming. The MIT Press, Cambridge, MA, 1989.
- P. Van Hentenryck and M. Dincbaa. Domains in Logic Program- ming. In AAAI-86, Philadelphia, PA, August 1986.
- D. Walt.. Generating Semantic Descriptions from Drawings of Scenes with Shadows. Technical Report Al271, MIT, MA, 1972.
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
1 Introduction
Many important problems in areas like artificial intelli gence, operations research and hardware desi&n can be viewed as . Constraint Satisfaction Problems (CSP). A CSP is defined by a finite set of variables taking val ues from finite domains and a set of constraints between these variables. A solution to a CSP is an assignment of values to variables satisfying all constraints and the problem amounts to findin.s one or all solutions. Most problems in this class are N'P-complete which mean that backtracking search is an important technique for solv ing them.
Many search algorithms (e.g. [1, 4, 5, 6, 9, 15]), preprocessing techniques and constraint algorithms (e.g.
"Supported by the Belgian National Fund for Scientific
Research u a Research ABBOciate.
Pascal Van Hentenryck Brown University, Box 1910, Providence, RI 02912 Email: pvh@cs.brown.edu
[20, 14, 10, 12, 13]) have been designed and anal ysed for this class of problems. See the reviews [11, 16] for a comprehensive overview of this area. In this paper, we are mainly concerned with (network) consis tency techniques, and arc consistency in particular. Con sistency techniques are constraint algorithms that reduce the search space by removing, from the domains and con straints, values that cannot appear in a solution. Arc consistency algorithms work on binary CSP and make sure that the constraints are individually consistent. Arc consistency algorithms have a long story on their own. They originates from Waltz filtering algorithm [20] and were refined several times [10] to culminate in the opti mal algorithm AC-4 of Mohr and Henderson [13]. AC-4 runs in O(ed 2 ) where e is the number of arcs in the net work and d is the size of the largest domain.
Consistency techniques have recently 1 been applied in the design of Constraint Logic Programming (CLP) lan guages, more precisely in the design and implementa tion of CHIP [18, 3]. CHIP allows for the solving of a variety of constraints over finite domains, including nu merical, symbolic, and user-defined constraints. It has been applied to a variety of industrial problems preserv ing the efficiency of imperative languages, yet shorten ing the development time significantly. Examples of ap plications include graph-coloring, warehouse locations, car-sequencing and cutting stock (see for instance [2, 18]). The kernel of CHIP for finite domains is an arc consistency algorithm, based on AC-3, for a set of ba sic binary constraints. Other (non-basic) constraints are approximated in terms of the basic constraints.
This research originated as an attempt to improve fur ther the efficiency of the kernel algorithm. This paper contains two contributions.
First we present a new generic arc consistency algo rithm AC-5. The algorithm is generic in the sense that it is parametrized on two procedures that are specified but whose implementation is left open. It can be reduced to AC-3 and AC-4 by proper implementations of the two procedures. Moreover, we show that AC-5 can be spe cialized to produce an O(ed) arc consiste,ncy algorithm for two important classes of constraints: functional and monotonic constraints.
Second we show that the kernel of CHIP consists pre cisely of functional and monotonic constraints and that AC-5, in conjunction with node consistency, provides a decision procedure for the basic constraints running in time O(ed).
1 Although Mackworth already mentioned as early as 1977 [10] the potential value of consistency techniques for program ming languages.
The rest of this paper is organized in the following way. Section 2 fixes the notation used in this paper ~ and contains the basic definitions. Section 3 describes the generic arc consistency algorithm AC-5 and speci fies two abstract procedures ARcCoNs and LOCALAR cCONS. Sections 4 and 5 show how an O(ed) algorithm can be achieved for functional and monotonic constraints by giving particular implementations of the two proce dures. Section 6 presents various representations for the domains while Section 7 shows that AC-5, in conjunction with node consistency, provides an O(ed) decision proce dure for the basic constraints of CLP over finite domains. Section 8 contains the conclusion of this research.
2 Preliminaries
To describe the CSP, we take the following conven tions. Variables are represented by the natural numbers 1, ... , n. Each variable i has an associated finite domain D1· All constraints are binary and relate two distinct variables. If i and j are variables { i < j), there is at most one constraint relating them. Th1s constraint is denoted Cij· As usual, C,;(v, w) denotes the boolean value ob tamed when variables i and j are replaced by values v and w respectively. We also denote D the union of all domains and d the size of the largest domain.
Arc consistency algorithms generally work on the graph representation of the CSP. We associate a graph G to a CSP in the following way. G has a node i for each variable i. For each constraint C,; relating variables i and j (i < j), G has two directed arcs, (i,j) and (j,i). The constraint associated to arc ( i, j) is C,; while the constraint associated· to (j, i) is ci' which is similar to C1; except that its arguments are mterchanged. We de note bye the number of arcs in G. We also use arc( G) and node( G) to denote the set of arcs and the set of nodes of graph G.
We now reproduce the standard definitions of arc con sistency for an arc and a graph.
~efinition 1 Let ( i, j) E arc( G). Arc ( i, j) is arc. con !t!tent wrt D, and D; 1fl' 'v'v E D,, 3w E D; : C,; ( v, w}.
Definition 2 Let P be D1 X ··· x Dn. A ~raph G is arc comi!tent wrt P iff 'v' ( i, j) E arc( G) : ( i, j) is arc consistent wrt D1 and D;. .
The next definition is useful to specify the outcome of an arc consistent algorithm.
Definition 3 Let P be Dt x ... x Dn. Let P' ~ P. Q is a maximally arc consistent wrt P' in P iff G is arc comi!tent wrt P' and there is no other P" with P' C P" ~ P such that G is arc consistent wrt P".
The purpose of an arc consistency algorithm is to com pute, given a graph G and a set P 1 a set P' such that G is maximally arc consistent wrt P in P.
3 The new Arc Consistency Algorithm
All algorithms for arc consistency work with a queue containing elements to reconsider. In AC-3, the queue contains arcs ( i, j) while AC-4 contains pairs ( i, v) where i is a node and v is a value. The novelty in AC-5 is to have a queue containing elements < ( i, j), w > where ( i, j) is an arc and w is a value which has been removed from D; and justifies the need to reconsider arc ( i, j). As procedure INITQUEUE( out Q)
Pod: Q = {}. function EMPTYQUEUE(in Q): Boolean Po6t: EMPTYQUEUE # ( Q = {} ). procedure ENQUEUE(in i, fl., inout Q) Pre: fl. ~ D; and i E node( G). ·
Po6t: Q = Qo U {<(A:, i), v >I (A:, i) E arc( G) and v E fl.}.
procedure DBQUEUE(inout Q, out i, j, w)
Po6t: < (i,j),w >E Qo and Q = Qo\ < (i,j),w >.
Figure 1: The QUEUE Module
procedure ARcCoNs(in i, j, out fl.)
Pre: ( i, j) E arc( G). Po6t: fl.= {v ED; I Vw ED;: -,C;;(v,w)}. procedure LocALARcCoNs(in i, j, w, out fl.) Pre: (i,j) E arc( G) and w ~ D;. Po6t: ll.1 C fl. C ll.2, with ll.1 =-{v ED; I C;;(v,w) and Vw' ED;: -,C;;(v,w')}, A2 ={~ED; I Vw' ED;: -,C;;(v,w')}.
Figure 2: Specification of the Procedures
a consequence, AC-5 can be specialized to obtain either AC-3 or AC-4 by giving a particular implementation of Procedures ARcCoNs and LocALARcCoNs. Moreover, for certain class of·constraints, AC-5 can be specialized to give an 0( ed) algorithm.
To present AC-5; we proceed in several steps. We first present the necessary operations on queues. Then we give the specification of the two abstract procedures ARCCONS and LOCALARCCONS. Finally we present the algorithm itself and prove a number of results.
3.1 Operations on Queues
The operations we need are described in Figure 1. Procedure INITQUEUE simply initializes the queue to an empty set. Function EMPTYQUEUE tests if the queue is empty. Procedure ENQUEUE(i,.tt., Q) is used when the set of values .6. has been removed from D1. It introduces elements of the form< (A:, i), v > in the queue Q where ( k, i) is an arc of the constramt graph and v E .6.. Proce dure DEQUEUE dequeues one element from the queue. In all specifications, we take the convention that a parame ter p subscripted with 0 (i.e., Po) represents the value of p at call time.
All these operations on queues but Procedure EN QUEUE can be achieved in constant time . . Procedure ENQUEUE can be implemented to run in 0(!) where ! is the size of .6.. The only difficulty in fact is Proc~ dure ENQUEUE. It requires a direct access from a vari able to its arcs (which is always assumed in arc con sistency algorithms) and a lazy distribution of v on the arcs. To achieve. this result, the queue could be organized to contain elements of the form < v, {At, ... , Am t > where At is an arc and v is a value. Procedure ENQUEUE(i, .6., v) adds an element < v, {At, ... Am}> to the queue, where the At are arcs of the form (j, i), for each v E .6.. Procedure DEQUEUE picks up an element < w, {At, ... , Am}> with m > 0, remove an At = (i, j) from the set, and returns i, j, and w.
3.2 Specification of the Parametric Procedures
Figure 2 gives the specification of the two subprob lems. Their implementations for various kinds of con-
Algorithm AC-5 Po8t: let 'Po = Dt 0 X ·.· X D .. 0 , 1' = Dt X ··· X D .. g is maximally arc consistent wrt 1' in 'Po. begin AC-5 1 INITQUEUE(Q) 2 for each ( i, i) E arc( G) do 3 begin 4 ARcCoNs(!,j,6); 5 ENQUEUE(·,6,Q); 6 RBMoVB(6,D;) 7 end; 8 while not EMPTYQUEUE(Q) do 9 begin 10 DEQUEUE(Q,i,j,w); 11 LocALARcCoNs(i,j,w,6); 12 ENQUEUE(i,6,Q); 13 R.BMOVE(6,D;) 14 end end AC-5
procedure INITQUEUE( out Q) Pod: V (k, i) E arc( G) : Stattu[(k, i), 11] =present i£ 11 ED; =rejected i£ 11 fl. D; function EMPTYQUEUE(in Q) Po8t: V (k, i) E arc( G) V11 : Stattu[(k, i), 11] of: suspended. procedure ENQUEUE(in i, 6, inout Q) Pre: V (k, i) E arc( G) "111 E 6: Statu·[( A:, i), v] =present. Po8t: V (k, i) E arc( G) "111 E 6 : Statu·[( A:, i), 11] = suspended. procedure DEQUEUE(inout Q, out i, J, w) Po8t: Statu·[(i, j), w] =rejected.
straints will be given in the next sections. They can also be specialized to produce AC-3 and AC-4 from AC-5.
Procedure ARcCoNs(i,j,~) computes the set of val ues ~ for variable i that are not supported by D;. Pro cedure LoCALARcCoNs(i,j,w,~) is used to compute the set of values in D, no longer supported because of the removal of value w from D;.
Note that the specification of LocALARcCoNs gives us much freedom for the result ~ to be returned. It is sufficient to compute ~1 to guarantee the correctness of AC-5. However the procedure gives the opportunity to achieve more pruning (up to ~:1) while still preserving the soundness of the algorithm. Interestingly enough, the ability to achieve more pruning turns out to be fun damental, for some classes of constraints (e.g. monotonic constraints), in producing an O(ed) algorithm.
3.3 Algorithm AC-5
We are now in position to present Algorithm AC-5. The algorithm is depicted in Figure 3 and has two main steps. In the first step, all arcs are considered once and arc consistency is enforced on each of them. Procedure REMOVE(~, D) removes the set of values~ from D. The second step applies LOCALARCCONS on each of the el ement of the queue possibly generating new elements in the queue. The correctness of the algorithm is an imme diate consequence of the correctness of Algorithm AC3 [10] that it generalizes. AC-3 is a particular case of AC-5 where the value w is never used in the implemen tation of Procedure LOCALARCCONS. AC-4 is a partieular case of AC-5 where the implementation of Proce dure LocALARcCoNs does not use node i. Of course; the data-structures used in AC-4 are more sophisticated than those of AC-3.
In order to prove various results on AC-5, we introduce a new data-structure STATUS which is a two-dimensional array, the first dimension being on arcs and the second on values. We also give the effect of the procedures manip ulating the queue on STATUS in Figure 4. Note that the actual implementation does not need to perform these operations. They are just presented here to ease the presentation and simplify the theorem.
Algorithm AC-5 preserves the following invariant on lines 2 and 8 for STATUS.
STATUS[(k,i), 11) =present jjf 11 ED;, = suspendedif£11¢ D; &l ((k,i),11} E Q, =rejected jjf 11 ¢ D; & ((k, i), 11} fl. Q.
We are now in position to prove the following theorem.
Theorem 4 Algorithm AC-5 has the following three properties: (1) The invariant on data-structure STATUS holds on lines 2 and 8. (2) AC-5 enqueues and dequeues at most O(ed) elements and hence the size of the queue is at most O(ed). (3) If 81 , .·· , 8p are the size of~ on each iteration at lines 12, then 8 1 + ... + 8p ~ O(ed).
Proof
Property 1 holds initially. Assuming that it holds in line 2, it also holds after an iteration of lines 4 to 6. Line 5 makes sure that < (j, i), v > is suspended for all v E ~ and put them on the queue while line 6 removes ~ from D,. So the invariant holds at the first execution of line 8. Execution of lines 10 to 13 preserves the invariant. Lines 10 and 11 maintain it on their own. Lines 12 and 13 respectively make sure that < (j, i), v > is rejected for all v E ~ and remove ~ from D,.
Property 2 holds because each element of STATUS is only allowed to make two transitions: one from present to suspended through Procedure ENQUEUE and one from suspended to rej acted throu~h Procedure DE QUEUE. Hence there can only be 0( ed) dequeues and enqueues.
Property 3 is a direct consequence of Property 2 and the preconditions of ENQUEUE on the data-structure STATUS. 0
The above theorem can be used to deduce the over all complexity of AC-5 from the complexity of Proce dures ARCCONS and LOCALARCCONS. In particular, in AC-3 and AC-4, Procedure ARCCONS is necessar ily O(d:l) which implies that the overall complexity is at least O(ed:l) since lines 4 to 6 are executed e times. There is no other possibility to reduce the complexity than considering particular classes of constraints, allow ing to implement, in particular, Procedure ARCCONS in O(d). Note also that an algorithm in O(ed) will be optimal for a subclass of constraints since it is reason able to assume that we need to check at least once each value in each domain. In the next two sections, we char acterize two classes of constraints that guarantee that Procedure ARcCoNs is O(d) and Procedure LocALAR cCONS is linearly related to the size of its output set ~ resulting in an AC-5 algorithm for these classes, running in time O(ed). In these sections, we assume a number of primitive operations on domains that are depicted in Figure: 5. As the reader will notice, the operations we define on the domains are more sophisticated than those usually required by arc consistency algorithms. In par ticular, they assume a total ordering on the domain D
procedure RBMoVBELBM(in v, inout D) Pod: D =Do\ {v}. function MBMBBR(in v, D): Boolean Pod: MEMBER <=> (v E D). function MIN(in D): Value Pod: MIN= min{11 ED}. function MAx(in D): Value Po1t: MAX= m11z{11 ED}. function Succ(in 11, D): Value Po1t: Succ = min{11' ED l11' > v}. function PRBD(in 11, D): Value Pod: PRBD = m11z{11' ED l11' < 11} Figure 5: The DoMAIN module procedure ARcCoNs(in i, j, out .6.) begin 1 .6. ·-8· 2 fo~-;a~h 11 E Di do 3 if /i;(11) rJ. D; then 4 .6. := .6. u { 11} end
for reasons that will become clear later. 2 The additional sophistication is necessary to achieve the bound 0( ed) for monotonic constraints. These primitive operations are assumed to take constant time.
4 Functional Constraints
Definition 5 A constraint C is functional wrt a domain D iff for all v (reap. w) E D there exists at most one w (reap. v) E .b such that C(v, w);
Note that the above definition is parametrized on a domain D. Some constraints might not be functional in general but become functional when restricted to a domain of values.
Convention 6 If C is a functional constraint, we de note by fc(v) the value w such that C(v, w) and f0 1 (w) the value v such that C( v, w ). Since AC-5 works on arcs, we associate a function fi; to each arc ( i, j) in such a way that, for constraint Ci;, arc (i,j) is assigned fc,; and arc (i, i) is assigned fa,~.
The results presented in the paper assume that it takes constant time to compute the functions fc and f0 1 in the same way as arc consistency algorithms assume that C(v, w) can be computed in constant time.
We are now in position to present Procedures ARC CONS and LOCALARCCONS for functional constraints. They are depicted in Figures 6 and 7.
It is clear that the procedures fulfill their specifica tions. Only one value per arc needs to be checked in Procedure ARCCONS since the constraint is functional. Procedure LOCALARCCONS computes the set .6.1 in this case and only one value needs to be checked. Proce dures ARCCONS and LocALARcCoNs are respectively O(d) and 0(1) for functional constraints. Hence we have an optimal algorithm.
2 Note that if D ia made up ofseveral unconnected domains with distinct orderings, it ia always possible to transform the underlying partial ordering into a total ordering.
procedure LocALARcCoNs(in i, j, w, out .6.) begin 1 if /;i(w) E Di then 2 .6. := {/;i(w)} 3 else 4 a := 0 end
procedure ARcCoNs(in i, j, out .6.) begin 1 2 3 4 .6. := 8; for each 11 E Di do end if-, Ci;(v,/ir.t(D;)) then .6. := .6. U {v}
Theorem 7 Algorithm AC-5 is O(ed) for functional constraints wrt D.
Note that functional constraints do not add any re quirement for the basic operations on the domains com pared to traditional algorithms.
5 Monotonic Constraints
We now consider another class of constraints in this sec tion. This class of constraints requires a total ordering < on D, as mentioned previously. Moreover we assume that, for any constraint C and element v E D, there exists elements w1 , w2 (not necessarily in D) such that C( v, w1) and C( w2, v) hold. This last constraint is used to simplify the algorithms but it is not restrictive in na ture.
Definition 8 A constraint C is monotonic wrt D iff there exists a total ordering on D such that, for any value v, w in D, C( v, w) holds implies C( v', w') holds for all values v', w' in D such that v' :$ v and w' ;::: w.
Convention 9 Since AC-5 is working with arcs, we as sociate to each arc ( i, j) three functions fi;, first,;, and nezt,; and a relation >-i;. Given a monotonic constraint C,;, the functions and relation for arc ( i, j) are as fol lows fi;(w) = maz{v I C(v, w)}, first,; = MAX, nezt,; = PRED, h; = > while those for arc (j, i) are f;,(v) min{w I C(v, w)}, first;, = MIN, nezt;, = Succ, >-;i = < . Moreover, since Procedures ARcCoNs and LOCALARc CoNS only use f·;, first,;, nezt,;, and h; for arc ( i, j),
procedure LocALARcCoNs(in i, j, in w, out .6.) begin 1 .6. ·- 8· 2 v :~ Jir.t(Di); 3 while 11 >- f(fir.t(D;)) do 4 begin 5 .6. := .6. U {11}; 6 v := nezt( 11, Di) 7 end end
Let S = {b, ... , B} D, = { v1, ... , v ... } ~ S with VII < VHl a.nd m > 0. Syntax D,.min : integer E S D,.ma.z : integer E S D,.element : a.rra.y [b ... B] of boolea.ns D, .· ucc : a.rra.y [b ... B] of integers E S D,.pred : a.rra.y [b ... B] of integers E S Semantics D,.min = v1 D,.ma.z = v ... D,.element[v] iff v E D, D, .· ucc[v~a] = Vll+l (1 $ lc < m) D,.pred[v,+d = v, (1 $ lc < m)
we omit the subscripts in the presentation of the algo rithms.
We are now in position to describe the implementa tion of Procedures ARCCONS and LOCALARCCONS for monotonic constraints. They are depicted in Figures 8 and 9.
Lemma 10 Procedures ARCCONS and LOCALARC CoNS fulfill their specifications.
Proof The result for Procedure ARC CONS follows from the monotonicity of the constraint that make sures that the value v can be checked only wrt an extremal value (minimum or maximum depending on the arc).
Procedure LocALARCCONS computes the set !:l. {v E D, I v >- f(first(D; ))}. By monotonicity of the constraint, !:l. ~ ll.2, and ll.2 n {v E D, I v j f(first(D; ))} = 0. Hence !:l. = ll.2 and the postcon dition is satisfied. 0
Note that, for monotonic constraints, it is more com plicated to compute the set ll.1 as we have no guarantee that the extremal value corresponding to w for variable i is in its domain. If the value is not in the domain, then we have no way to use Procedures PRED and Succ, and this leads to a non-optimal al~orithm.
Procedures ARcCoNS is Otd). Procedure LocALAR cCONS has as many iterations in lines 5 and 6 as ele ments in the resulting set ll.. Hence it follows that we have an optimal algorithm.
Theorem 11 Procedure AC-5 is O(ed) for monotonic constraints wrt D.
It is also clear that AC-5 can be applied at the same time to functional and monotonic constraints keeping the same complexity.
6 Implementation of Domain
In the previous sections, we assume that the primi tive operations on domains can be performed in constant time. In this section, we present two data-structures that enable to achieve this result.
The first data-structure assumes a domain of consec utive integer values and is depicted in Figure 10. The fields min and maz are used to pick up the minimum and maximum values, the field element to test if a value is in the domain, and the two fields pred and succ to access in constant time the successor or predecessor of a value in the domain. The operation REMOVEELEMENT must take care updating all fields to preserve the semantics. This can be done in constant time.
When the domain is sparse, the representation is ba sically the same but it reasons about indices instead of values and uses an hash-table to test membership to the domain. Although the time complexity of membership is theoretically not 0(1), under reasonable assumption, the expected time to search for an element is 0(1).
7 Application
We describe the application of AC-5 to Constraint Logic Programming over finite domains.
Constraint Logic Programming [7] is a class of lan guages whose main operation is constraint-solving over a computation domain. A step of computation amounts to check the satisfiability of a conjunction of constraints.
Constraint Logic Programming over finite domains has been investigated in [19, 17, 18]. It is a com putation domain where constraints are equations, in equalities and disequations over natural number terms or equations and disequations over constants. Natu ral number terms are constructed from natural num bers, variables ranging over a finite domain of natural numbers, and the standard arithmetic operators ( +, x, .. .. ). Also some symbolic constraints are provided to increase the expressiveness and the user has the abil ity to define its own constraints. This computation do main is available in CHIP [3] and its constraint-solver is based on consistency techniques, arithmetic reasoning, and branch & bound. It has been applied to numer ous applications in combinatorial optimization such as graph-coloring, warehouse location, scheduling and se quencing, cutting-stock, assignment problems, and mi crocode labeling to name a few (see for instance [2, 18].
Space does not allow us to present the operational se mantics of the language. Let us just mention that the kernel of the constraint-solver is an arc consistency al gorithm for a set of basic constraints. Other (non-basic) constraints are approximated in terms of the basic con straints and generate new basic constraints. The basic constraints are either domain constraints or arithmetics constraints, and are as follows (variables are represented by upper case letters and constants by lower case letters):
- domain constraint: X E { a1, ... , a,.};
- arithmetic constraints: aX ::p b, aX = bY + c, aX~ bY+ c, aX~ bY+ c with a,at,b,c ~ 0 and a ::p o.
These constraints have been chosen carefully in order to avoid having to solve an .N'P-complete constraint sat isfaction problem. For instance, allowing two variables in disequations or three variables in inequalities or equa tions leads to .N'P-complete problems.
We now show that AC-5 can be the basis of an efficient decision procedure for basic constraints.
Definition 12 A system of constraints S is a pair (AC, DC) where AC is a set of arithmetic constraints and DC is a set of domain constraints such that any variable occurring in an arithmetic constraint also oc curs in some domain constraint of S.
Definition 13 Let S = (AC, DC) be a system of con straints. The set Dz is the domain of z in S (or in DC) iff the domain constraints of z in DC are :z: E D1, ... , :z: E D1r. and Dz is the intersection of the D, 's.
Let us define a solved form for the constraints.
Definition 14 Let S be a system of constraints. Sis in 1olved form iff any unary constraint C(X) in S is node consistent 3 wrt the domain of X in S, and any binary constraint C(X, Y) inS is arc consistent wrt the domains of X,Y inS.
We now study a number of properties of systems of con straints in solved form.
Property 15 Let C(X, Y) be the binary constraint aX ~ bY + c or aX ~ bY + c, arc consistent wrt Dx = { v1, ··· , vn}1 Dy = { w1, ··· , wm}· Assume also that v1 < ... < Vn and w1 < ... < Wm· Then we have Cis monotonic and C(v11 w1) and C(vn, wm) hold.
Property 16 Let C(X, Y) be the binary constraint aX = bY + c with a b =/; 0, arc consistent wrt Dx = { v1, ··· , Vn}, Dy = { w1, ··· , wm}· Assume also that v1 < ... < Vn and w1 < ... < Wm· Then we have C is functional, n = m, and C(v,, w,) holds.
The satisfiability of a system of constraints in solved form can be tested in a straightforward way.
Theorem 17 Let S = (AC, DC) be a system of con straints in solved form. S is satisfiable iff (0, DC) is satisfiable.
Proof It is clear that (0, DC) is not satisfiable iff the domain of some variable is empty in DC. If the domain of some variable is empty in DC, then S is not satisfi able. Otherwise, it is possible to construct a solution to S. By properties 15 and 16, all binary constraints of S hold if we assign to each variable the smallest value in its domain. Moreover, because of node consistency, the unary constraints also hold for such an assignment. 0
It remains to show how to transform a system of con straints into an equivalent one in solved form. This is precisely the purpose of the node and arc consistency algorithms.
Algorithm 18 To transform the system of constraints S into a system in solved form S':
- apply a node consistency algorithm to the unary constraints of S = (AC, DC) to obtain (AC, DC');
- apply an arc consistency algorithm to the binary constraints of (AC, DC') to obtainS' = (AC, DC").
Theorem 19 Let S be a system of constraints. Algo rithm 18 produces a system of constraints in solved form equivalent to S.
We now give a complete constraint-solver for the basic constraints. Given a system of constraints S, Algorithm 20 returns true if S is satisfiable and falle otherwise.
Algorithm 20 To check the satisfiability of a system of constraints S: (1) apply Algorithm 18 to S to obtain S' = (AC, DC) and (2) if the domain of some variable is empty in DC', return fal1e; otherwise return true.
In summary, we have shown that node and arc consis tency algorithms provide us with a decision procedure for basic constraints. The complexity of the decision proce dure is the complexity of the arc consistency algorithm. Using the specialization of AC-5 for basic constraints, we obtain an O(ed) decision procedure.
3 As usual, a unary constraint C is node con.fident wrt D iff Vv ED: C(v).
8 Conclusion
A new generic arc consistency algorithm AC-5 has been presented whose specializations include, not only AC3 and AC-4, but also an 0( ed) algorithms for an im portant subclass of networks containing functional and monotonic constraints. An application of AC-5 to Con straint Logic Programming over finite domains has been described. To~ether with node consistency, it provides the main algonthms for an O(ed) decision procedure for basic constraints. From a software engineering perspec tive, AC-5 has the advantage of uniformity. Each con straint may have a particular implementation, based on AC-3, AC-4, or some specific techniques, without influ encing the main algorithm. As a consequence, many different implementation techniques can be interleaved together in a natural setting.
Future research on this topic includes the search for other subclasses whose properties allow for an 0( ed) al gorithm. Path consistency has not been considered seri ously in CLP languages and generalizations of the above ideas to path consistency and support for path consis tency in CLP languages deserve future attention. Fi nally, while arc-consistency of functional constraints can also be solved through a reduction to 2-sat [8], it is an open issue to find out if a similar reduction exists for monotonic constraints. ·
@inproceedings{ijcai1991p49,
title = {An Efficient Arc Consistency Algorithm for a Class of CSP Problems},
author = {Deville, Yves and Van Hentenryck, Pascal},
booktitle = {Proceedings of the Twelfth International Joint Conference on
Artificial Intelligence, {IJCAI-91}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {John Mylopoulos and Ray Reiter},
pages = {325--329},
year = {1991},
month = {8},
note = {Automated Reasoning},
url = {https://ijcai.org/proceedings/1991/49},
}
TY - CPAPER TI - An Efficient Arc Consistency Algorithm for a Class of CSP Problems AU - Deville, Yves AU - Van Hentenryck, Pascal T2 - Proceedings of the Twelfth International Joint Conference on Artificial Intelligence, IJCAI-91 PB - International Joint Conferences on Artificial Intelligence PY - 1991 SP - 325 EP - 329 UR - https://ijcai.org/proceedings/1991/49 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: