Reformulation of Global Constraints Based on Constraints Checkers
Contents
1. if the automaton uses one single counter the sweep algorithm must consider each pair of transition constraints sharing variables and arc consistency on each constraint will lead to a complete filtering for our global constraint 3 2 Complexity Our approach allows the representation of a global constraint by a network of con straints of small arities As seen in the previous section the filtering obtained using this reformulation of the global constraint depends on the filtering performed by the solver If the solver maintains arc consistency using the general schema 29 30 the complex ity is in O er d where e is the number of constraints r the maximum arity and d the size of the largest domain However this is a rough bound and the practical time com plexity can be far from this limit Indeed the constraints have very different arities and some domains involve only very few values Furthermore on some constraints a spe cialized algorithm can be used to reduce the filtering cost Finally one would want to enforce only a partial form of arc consistency a directional arc consistency for exam ple in the case of a Berge acyclic constraint network or a stronger filtering enforcing We assume here that the cost of a constraint check is linear in the constraint arity while it is sometimes assumed to be constant pairwise consistency for example on a constraint network having a join tree Both the pruning efficiency and the comple2. lex lesseq can be expressed as built in 1ex chain constraints The results are presented in three scatter plots in Figure 4 Each graph compares times for finding all solutions to a ran dom constraint instance using a randomly chosen labeling strategy The X coordinate of each point is the runtime for an automaton reformulation The Y coordinate is the runtime for a decomposition into built in constraints A line least square fitted to the data points is shown in each graph Runtimes are in seconds From these experiments we observe that an automaton reformulation typically runs a few times slower than its hard coded counterpart roughly the same ratio as between interpreted and compiled code in a typical programming language This slowdown is likely to have much less impact on the overall execution time of the program The conclusion is that the automaton reformulation is a feasible and very reasonable way of rapidly prototyping new global constraints before embarking on developing a specific filtering algorithm should that be deemed necessary 4 Applications of this Technique 4 1 Designing Automaton Reformulations for Global Constraints We apply this new methodology for designing automaton reformulations for the fol lowing fairly large set of global constraints We came up with an automaton for the following constraints gt These automata are available in the technical report 24 All signature constraints are encoded in ord
3. topes In T Walsh editor Principles and Practice of Constraint Programming CP 2001 volume 2239 of LNCS pages 392 407 Springer Verlag 2001 N Beldiceanu and E Poder Cumulated profiles of minimum and maximum resource utili sation In Ninth Int Conf on Project Management and Scheduling pages 96 99 2004 J Cohen Non deterministic algorithms ACM Computing Surveys 11 2 79 94 1979 G J Woeginger Exact algorithms for NP hard problems A survey In M Juenger G Reinelt and G Rinaldi editors Combinatorial Optimization Eureka You shrink vol ume 2570 of LNCS pages 185 207 Springer Verlag 2003
4. 38 353 366 1989 D Maier The Theory of Relational Databases Computer Science Pres Rockville MD 1983 C Berge Graphs and hypergraphs Dunod Paris 1970 P Janssen and M C Vilarem Probl mes de satisfaction de contraintes techniques de r solution et application la synth se de peptides Research Report C R 1I M 54 1988 P J gou Contribution l tude des probl mes de satisfaction de contraintes algorithmes de propagation et de r solution Propagation de contraintes dans les r seaux dynamiques PhD Thesis 1991 N Beldiceanu M Carlsson and T Petit Deriving filtering algorithms from constraint checkers Technical Report T2004 08 Swedish Institute of Computer Science 2004 C Beeri R Fagin D Maier and M Yannakakis On the desirability of acyclic database schemes JACM 30 479 513 1983 R Dechter and J Pearl Tree clustering for constraint networks Artificial Intelligence 38 353 366 1989 R Fagin Degrees of acyclicity for hypergraphs and relational database schemes JACM 30 514 550 July 1983 N Beldiceanu and M Carlsson Sweep as a generic pruning technique applied to the non overlapping rectangles constraints In T Walsh editor Principles and Practice of Constraint Programming CP 2001 volume 2239 of LNCS pages 377 391 Springer Verlag 2001 C Bessi re E C Freuder and J C R gin Using constraint metaknowledge to reduce arc consistency computation Artificial Intelligence
5. Vs entails a minimum violation cost of 2 Observe that for this constraint the signature variables So Si 5 3 Sa Ss S6 are Vo Vi V2 V3 Va Vs Ve As in the algorithm of Pesant 6 our consistency algorithm builds a layered acyclic directed multigraph G Each layer of G contains a different node for each state of our automaton Arcs only appear between consecutive layers Given two nodes n and n2 of two consecutive layers q and q denote their respective associated state There is an arc a from n to n iff in the automaton there is an arc arc q1 v q2 from q to q2 The arc a is labeled with the value v Arcs corresponding to transitions that cannot be triggered according to the current domain of the signature variables So Sm 1 are marked as infeasible All other arcs are marked as feasible Finally we discard isolated nodes from our layered multigraph Since our automaton has a single initial state and a single final state G has one source and one sink denoted by source and sink respectively Example 5 continued Part A of Fig 7 recalls the automaton of the global_contiguity constraint while part B gives the multigraph G associated with the soft_global_contiguity constraint previously introduced Each arc is labeled by the condition associated to its correspond ing transition Each node contains the name of the corresponding automaton state Numbers in a node will be explained later on Infeasible arcs are represent
6. for which filtering algorithms already exist Note also that all previous work restricts a transition of the automaton to checking whether or not a given value belongs to the domain of a variable In contrast our approach permits to associate any constraint to a transition As a consequence we can model concisely a larger class of global constraints and prove properties on the consistency by reasoning directly on the constraint hypergraph As an illustrative ex ample consider the lexicographical ordering constraint between two vectors As shown by Fig 1 we come up with an automaton with two states where a transition constraint corresponds to comparing two domain variables Now if we forbid the use of compari son this would lead to an automaton whose size depends of the number of values in the domains of the variables Our second contribution is to provide for a restricted class of automata an automa ton reformulation for the relaxed case This technique relies on the variable based vio lation cost introduced in 7 8 This cost was advocated as a generic way for expressing the violation of a global constraint However algorithms were only provided for the soft alldifferent constraint 7 We come up with an algorithm for computing a sharp bound of the minimum violation cost and with an automaton reformulation for pruning in order to avoid to exceed a given maximum violation cost Section 2 describes the kind of finite automaton used for recog
7. i lt vars i 1 vars i gt vars i 1 ct vars i vars i 1 D2 Fig 1 Four checkers and their corresponding automata Parts A1 B1 C1 and D1 of Fig 1 depict the four checkers respectively associated with global contiguity lt jex among and inflexion For each checker we observe the following facts Within the checker depicted by part A1 of Fig 1 the values of the sequence vars 0 vars n 1 are successively compared against 0 and 1 in order to check that we have at most one group of consecutive 1 This can be translated to the automaton depicted by part A2 of Fig 1 The automaton takes as input the sequence vars 0 vars n 1 and triggers successively a transition for each term of this sequence Transitions labeled by 0 1 and are respectively associated with the conditions vars i 0 vars i 1 andi n Transitions leading to failure are systematically skipped This is why no transition labeled with a starts from state z Within the checker given by part B1 of Fig 1 the components of vectors a and y are scanned in parallel We first skip all the components that are equal and then perform a final check This is represented by the automaton depicted by part B2 of Fig 1 The automaton takes as input the sequence x 0 y 0 a n 1 y n 1 and triggers a transition for each term of this sequence Unlike the global contiguity constraint some t
8. of such a constraint C we will show how to create the automata associated to the following constraints synchronizede U1 U2 Um Vi Vo Vm enforces that all positions where the automaton Ac recognizes a pattern in U1Us Um correspond exactly to the positions where Ac recognizes a pattern in Vi V2 Vm In other words the positions where both counters are incremented should coincide in both sequences distincte U1 U2 Um Vi V2 Vm enforces that all positions where the automaton Ac recognizes a pattern in U1Us U be distinct from all positions where Ac recognizes a pattern in Vi V2 Vm This means that the positions where a counter is incremented should all be distinct As an illustrative example consider the peak constraint which counts the num ber of peaks of a sequence of variables where adjacent variables are not equal The automaton of this constraint is depicted by part A of Fig 6 We explain how to derive the automaton associated to synchronizedg and to distincte from the automaton Ac associated to C Let A2 S Ac and D Ac re spectively denotes the automaton that is the product of Ac and Ac the automaton associated to synchronized and the automaton associated to distinctc Regarding the example of the peak constraint AZ is given by part B of Fig 6 We compute S Ac and D Ac from A2 Within A we partition its transitions into the following 4 classes A VAR lt VAR i
9. s arc s 2 i arc s 0 7 arc s t arc 4 1 arc i 2 i arc i 0 j c t 1p arc i t arc j 153 arc j 0 j arc j 2 i c t 11 arc j t The signature constraint relating each pair of variables vars i vars i 1 to the signature variable S is defined as follows Wintiexion Si vars i vars i4 1 vars i gt vars i 1 lt Si 0 vars i vars i 1 amp S 1 A vars i lt vars i 1 amp S 2 The sequence of transitions triggered on the ground instance inflexion 4 3 3 1 4 5 5 6 5 5 06 3 is s 3 386S9 1 3 1e 1 0 1 4eS 53 2 4 lt 5453 2 5 5GS4 1 5 6e85 2 ET E TER i i i 6 gt 5S6 0 5 5 amp S7 1 5 6e9S8 2 6 gt 3S9 0 i i d i t_ Each transition gives the c 2 c 3 CE ninf 4 corresponding condition and eventually the value of the counter c just after firing that transition 3 Automaton Reformulation The automaton reformulation is based on the following idea For a given global con straint C one can think of its automaton as a procedure that repeatedly maps a current state Q and counter vector E given a signature variable S to a new state Qi 1 and counter vector Tesi until a terminal state is reached We then convert this pro cedure into a transition constraint 6 Q Ri Si Qiri Rod as follows Q is a variable whose values correspond to the states that can be reached at step Simi larly K is a ve
10. to staff scheduling in health care In F Rossi editor CP 2003 Principles and Practice of Constraint Programming volume 2833 of LNCS pages 153 167 Springer Verlag 2003 M Maher Analysis of a global contiguity constraint In Workshop on Rule Based Constraint Reasoning and Programming 2002 held along CP 2002 A Frisch B Hnich Z Kiziltan I Miguel and T Walsh Global constraints for lexico graphic orderings In Pascal Van Hentenryck editor Principles and Practice of Constraint Programming CP 2002 volume 2470 of LNCS pages 93 108 Springer Verlag 2002 N Beldiceanu and E Contejean Introducing global constraints in CHIP Mathl Comput Modelling 20 12 97 123 1994 N Beldiceanu Global constraints as graph properties on structured network of elementary constaints of the same type In R Dechter editor CP 2000 Principles and Practice of Constraint Programming volume 1894 of LNCS pages 52 66 Springer Verlag 2000 M Carlsson et al S CStus Prolog User s Manual Swedish Institute of Computer Science 3 11 edition January 2004 http www sics se sicstus T Le Provost and M Wallace Domain independent propagation In Proc of the In ternational Conference on Fifth Generation Computer Systems pages 1004 1011 1992 http www icparc ic ac uk eclipse ILOG ILOG Solver Reference Manual 6 0 edition http www ilog com R Dechter and J Pearl Tree clustering for constraint networks Artificial Intelligence
11. 107 125 148 1999 C Bessi re J C R gin R H C Yap and Y Zhang An optimal coarse grained arc consis tency algorithm Artificial Intelligence 2005 to appear I P Gent and T Walsh CSPLib a benchmark library for constraints Technical Report APES 09 1999 APES 1999 nt tp www csplib org 32 33 34 35 36 37 38 39 40 M Carlsson G Ottosson and B Carlson An open ended finite domain constraint solver In H Glaser P Hartel and H Kuchen editors Programming Languages Implementations Logics and Programming volume 1292 of LNCS pages 191 206 Springer Verlag 1997 COSYTEC CHIP Reference Manual v5 edition 2003 P Refalo Linear formulation of constraint programming models and hybrid solvers In R Dechter editor Principles and Practice of Constraint Programming CP 2000 volume 1894 of LNCS pages 369 383 Springer Verlag 2000 N Beldiceanu and M Carlsson Revisiting the cardinality operator and introducing the cardinality path constraint family In P Codognet editor JCLP 2001 Int Conf on Logic Programming volume 2237 of LNCS pages 59 73 Springer Verlag 2001 G Ottosson E Thorsteinsson and J N Hooker Mixed global constraints and inference in hybrid IP CLP solvers In CP 99 Post Conference Workshop on Large Scale Combinatorial Optimization and Constraints pages 57 78 1999 N Beldiceanu Q Guo and S Thiel Non overlapping constraints between convex poly
12. 44 VARj VAR i44 VARi2VAR itl VARi2VAR itr C C 1 B UU V gt V Oy UL sr Vi lt Viga C C 1 UL Uiir Vi gt Vits C C 1 D D 1 Us gt Ue i atl Vi Viel C C 1 V V Vi Vii AA Ui SU aq Vi lt Vi 1 Uj U5 44 7 Vi 2Vi 41 U lt U V gt V 88 J su V lt V C SUie1 7 Vi Vit 201417 Vi Vi 1 U gt U 447 Uj lt Uj 417 Pisis UU EH V gt V V V 1 Vi ae t KO i dd z U Ur Vi Vii zi D Fig 6 Automaton associated to the peak constraint and derived automata Uy Ui 41 Miina i D D 1 Ness us Those transitions that do not increment any counter Those transitions that only increment the counter associated to the sequence U41U Um Those transitions that only increment the counter associated to the sequence Vi V2 Vm Finally those transitions that increment both counters S Ac corresponds to AZ from which we remove all transitions where only one single counter is incremented and D Ac corresponds to A2 from which we remove all transitions where both counters are incremented We also remove from the resulting automata all counter variables Coming back to the example of the peak constraint S Ac and D Ac respectively correspond to part C and D of Fig 6 5 Handling Relaxation for a Counter Free Automaton This section presents a filtering alg
13. Reformulation of Global Constraints Based on Constraints Checkers Nicolas Beldiceanu Mats Carlsson Romuald Debruyne and Thierry Petit 1 LINA FRE CNRS 2729 Ecole des Mines de Nantes FR 44307 Nantes Cedex 3 France Nicolas Beldiceanu Romuald Debruyne Thierry Petit emn fr SICS P O Box 1263 SE 164 29 Kista Sweden Mats Carlsson sics se Abstract This article deals with global constraints for which the set of solu tions can be recognized by an extended finite automaton whose size is bounded by a polynomial in n where n is the number of variables of the corresponding global constraint By reducing the automaton to a conjunction of signature and transition constraints we show how to systematically obtain an automaton re formulation Under some restrictions on the signature and transition constraints this reformulation maintains arc consistency An implementation based on some constraints as well as on the metaprogramming facilities of SICStus Prolog is available For a restricted class of automata we provide an automaton reformu lation for the relaxed case where the violation cost is the minimum number of variables to unassign in order to get back to a solution 1 Introduction Developing filtering algorithms for global constraints is usually a very work intensive and error prone activity As a first step toward a methodology for semi automatic de velopment of filtering algorithms for global constraints Carlsson and Beldic
14. a given state are mutually incompatible all au tomata are deterministic Let M denote the set of mutually incompatible conditions associated with the different transitions of an automaton Let Ao A1 denote the sequence of sequences of variables of C on which the transitions are successively triggered All these subsets contain the same number of elements and refer to some variables of C Since these subsets typically depend on the constraint we leave the computation of o A 1 outside the automaton To each subset A of this sequence corresponds a variable S with an initial domain ranging over min min M 1 where min is a fixed integer To each integer of this range corresponds one of the mutually incompatible conditions of M The sequences 9 45 1 and Ao Am 1 are respectively called the signature and the signature argument of the constraint The constraint between 5 and the variables of A is called the signature constraint and is denoted by Vc S A From a pragmatic point the view the task of writing a constraint checker is nat urally done by writing down an imperative program where local variables i e counters assignment statements and control structures are used This suggested us to consider deterministic finite automata augmented with counters and assignment statements on these counters Regarding control structures we did not introduce any extra feature since the deterministic choice of
15. acilities of SICStus Prolog 32 Example 4 Consider three variables x 0 1 y 0 3 z 0 1 2 3 subject to the con junction of constraints bet ween 0 3 1 x y z 1 0 2 exact1y one z y z 0 Even if both the bet ween and the exact 1y one constraints maintain arc consistency we need the automaton associated with their conjunction to find out that z 0 This can be seen as fol lows after two transitions the automaton 3 will be either in state ai or in state bi However in either state a 0 must already have been seen and so there is no support for z 0 The corresponding code is available in the technical report 24 l a j xj L b x I x in values e a 7X E bj7X O x not in values g aj X G bj x end f Fig 5 Automata associated with between and exactly one and the automaton associated with their conjunction 4 3 Designing Constraints between Two Sequences of Variables This section considers constraints of the form C N VAR1 VAR2 VARm for which the corresponding automaton Ac uses one single counter which is incremented by certain transitions and finally unified to variable N in the final state of Ac This corresponds to constraints that count the number of occurrences of a given pattern in a sequence VAR VA Rs VAR Each time the automaton recognizes a pattern in the sequence it increments its counter by 4 1 Given the automaton Ac
16. ansition constraint 9 are shown in part A of Fig 2 Example 3 Consider a among nvar vars values constraint First we need a signature con straint among relating each argument vars i to a signature letter S This can be done as follows Wamong Si vars i values vars i values S 1 vars i g values S 0 The automaton of among and the decision tree corresponding to the transition constraint Pamong are shown in part B of Fig 2 3 1 Complete Filtering when there is No Shared Variable between Signature Constraints In the general case local consistency such as arc consistency is not sufficient to ensure global consistency In other words there can be some locally consistent values that cannot be extended to a complete solution mainly because there can be some cycles in the constraint graph However we will highlight some special cases where local consistency can lead to global consistency We consider automata where all subsets of variables in SignatureArg are pairwise disjoint As we will see in the section many constraints can be encoded by such automata Without counters If there are no counters the automaton reformulation maintains arc consistency on this kind of automata provided that the filtering algorithms of the sig nature and transition constraints also maintain arc consistency To prove this property consider the constraint hypergraph that represents the conjunction of all signature and tra
17. ch condition is taken in one of the following set of conditions a lt i ai z a gt i b gt i bi vi b lt zi xj values x values This makes up to 3 3 2 18 possible combinations and leads to the signature constraint Wpetweennexactly one Si Qi vi bi values between the signature variable S and the i th component of vectors W X and b ai lt zi Abi gt xi A zi Z values 9 ifa lt vi A bi gt vi mi ai lt i A bi i A i values 10 ifa lt zi A bi vi A i ai lt i Abi lt i A xi Z values 11 ifa lt i Abi lt vi A i ai i A bi gt i A xi values 12 ifa zi b gt vi A Ti i values i i i ifa xi A bi zi A zi values 13 ifa zi b vi A i values i i i i values values values ai i A bi vi xi values 14 ifa vi A bi lt vi vi ai gt i Abi gt xi A xi values 15 ifa gt zi Abi gt vi mi aiD tiA br g A 2 values 16 ifa gt a b vi Ati ai gt i Abi mi A xi values 17 ifa gt i Abi lt vi mi values values values U E ll 0 d4O00 RONv Ao values In order to maintain arc consistency on the conjunction of the between a x b and the exactly one z values constraints we need to have arc consistency on WpetweenAexact ly one Si Qi Zi bi values In our context this is done by using the global constraint programming f
18. ct increase For instance inflexion 4 3 3 1 4 5 5 6 5 5 6 3 holds since we can extract from the sequence 33145565563 the four subsequences 314 565 6556 and 563 which all follow one of these two patterns We don t skip the checker since in the long term we consider that the goal would be to turn any existing code performing a check into a constraint global contiguity vars 0 n 1 BOOLEAN among nvar vars 0 BEGIN YAU BWNHE 1 BEGIN 2 i 0 3 WHILE i n AND vars i 0 DO i 4 WHILE i n AND vars i 1 DO i 5 WHILE i n AND vars i 0 DO i 6 RETURN i n 7 END A1 iex x 0 n 1 y 0 n 1 BOOLEAN 1 BEGIN 2 i 0 3 WHILE i lt n AND x i y i DO i 4 RETURN i n OR x i y i 5 END B1 n 1 values BOOLEAN i 0 c 0 WHILE i n DO IF vars i itt RETURN in values THEN c nvar c C1 END inflexion ninf vars 0 n 1 BOOLEAN 01 BEGIN i 0 c 0 WHILE i n 1 AND vars i vars i l DO i IF i n 1 THEN less vars i lt vars i l WHILE i lt n 1 DO IF less THEN I IF vars i gt vars i 1 ELSE I IF vars i vars i 1 itt RETURN END THEN c THEN c less TRUE ninf c D1 global_contiguity lt vars i lt vars it 1 less FALSE lex among vars i in values c p vars il e notin values A2 B2 C2 inflexion vars i vars i 1 vars i vars i 1 vars i vars i 1 vars
19. ctor of variables whose values correspond to the potential values of the counters at step 7 Assuming that the automaton associated with C has na arcs are qi 51 d fi K aTC qna Sna dha fas K the transition constraint has the following form V Qi aj Si 83 Qus d Ki BE Consider first the case when no counter is used i e the constraint is effectively c Qi Si Qi 1 This can be encoded with a ternary relation defined by extension e g SICStus Prolog s case 16 page 463 ECLiPSe s Propia 17 or Ilog Solver s table constraint 18 If that relation maintains arc consistency as does case it follows that c maintains arc consistency Consider now the case when one counter is used Then we need to extend the ternary relation by one argument corresponding to 7 This argument can be used as an index into a vector f1 K faa C selecting the value that pm should equal Thus to encode P we need a 4 ary relation defined by extension na arithmetic constraints to compute the vector and an element constraint to select a value from the vector As an optimization identical f Ki expressions can be merged yielding a shorter vec tor and fewer arithmetic constraints In general arc consistency can not be guaranteed for c Finally consider the case when two or more counters are used This is a straightfor ward generalization of the single counter case We can then arrive at a
20. e formulated as follows Given x decide whether there exists y so that y lt m x and R x y x is an instance of the problem y is a short YES certificate for this instance R x y is a polynomial time decidable relation that verifies certificate y for instance x and m x is a computable and polynomially bounded complexity parameter that bounds the length of the certificate y In our context if y is fixed and known is a global constraint and its y variables with their domains y is a solution to that global constraint R x y is an automaton which encodes a checker for that global constraint Acknowledgments We are grateful to I Katriel for suggesting the use of topological sort for the relaxation part and to C Bessi re for his helpful comments wrt Berge acyclic CSP s References 1 M Carlsson and N Beldiceanu From constraints to finite automata to filtering algorithms In D Schmidt editor Proc ESOP2004 volume 2986 of LNCS pages 94 108 Springer Verlag 2004 N R Vempaty Solving constraint satisfaction problems using finite state automata In Na tional Conference on Artificial Intelligence AAAI 92 pages 453 458 AAAI Press 1992 J Amilhastre Repr sentation par automate d ensemble de solutions de probl mes de satis faction de contraintes PAD Thesis 1999 J Amilhastre H Fargier and P Marquis Consistency restoration and explanations in dy namic CSPs application to configuration Artific
21. eanu in troduced 1 an approach to designing filtering algorithms by derivation from a finite automaton As quoted in their discussion constructing the automaton was far from obvi ous since it was mainly done as a rational reconstruction of an emerging understanding of the necessary case analysis related to the required pruning However it is commonly admitted that coming up with a checker which tests whether a ground instance is a so lution or not is usually straightforward As shown by the following chronological list of related work automata were already used for handling constraints Vempaty introduced the idea of representing the solution set of a constraint net work by a minimized deterministic finite state automaton 2 He showed how to use this canonical form to answer queries related to constraints as satisfiability validity i e the set of allowed tuples of a constraint or equivalence between two constraints This was essentially done by tracing paths in an acyclic graph derived from the automaton Later Amilhastre 3 generalized this approach to nondeterministic automata and introduced heuristics to reduce their size The goal was to obtain a compact repre sentation of the set of solutions of a CSP That work was applied to configuration problems in 4 Boigelot and Wolper 5 also used automata for arithmetic constraints Within the context of global constraints on a finite sequence of variables the rece
22. ed with a dotted line A Automaton for B Graph of potential executions of the automaton of global contiguity global contiguity according to So S1 S2 S4 S4 S5 Sg Fig 7 Relaxing the global_contiguity constraint We now explain how to use the multigraph G to evaluate the minimum violation cost Min and to prune the signature variables according to the maximum allowed violation cost max cost Evaluating the minimum violation cost Min can be seen as finding the path from the source to the sink of G that contains the smallest number of infeasible arcs This can be done by performing a topological sort starting from the source of G While performing the topological sort we compute for each node n of G the minimum number of infeasible arcs from the source of G to nz This number is recorded in before n At the end of the topological sort the minimum violation cost Min we search for is equal to before sink Notation 1 Let i be assignable to a signature variable Sj Mini denotes the minimum violation cost value according to the hypothesis that we assign i to Sj To prune domains of signature variables we need to compute the quantity Min In order to do so we introduce the quantity after n for a node n of G after n is the minimum number of infeasible arcs on all paths from n to sink It is computed 7 The acyclic graph is layered and no transitive arcs exist Therefore for each node n at a given layer k the quantity b
23. efore n is computed from the nodes of layer k 1 as follows for each n 1 such that there exists an arc from nz to nx we add 1 to before n 1 if it is an infeasible arc and 0 if it is a feasible arc Then be fore nx is the minimum of such computed quantities by performing a second topological sort starting from the sink of C Let Ai denote the set of arcs of G labeled by i for which the origin has a rank of l The quantity min before a after b represents the minimum violation cost under the hypoth a be A esis that S remains assigned to i If that quantity is greater than Min then there is no path from source to sink that uses an arc of A and that has a number of infeasible arcs equal to Min In that case the smallest cost we can achieve is Min 1 Therefore we have M inj min min before a after b Min 1 a be A The filtering algorithm is then based on the following theorem Theorem 3 Let i be a value from the domain of a signature variable Sj If Mini gt max cost then i can be removed from S The cost of the filtering algorithm is dominated by the two topological sorts They have a cost proportional to the number of arcs of G which is bounded by the number of sig nature variables times the number of arcs of the automaton Example 5 continued Let us come back to the instance of Fig 7 Beside the state s name each node n of part B of Fig 7 gives the values of before n and of aft
24. er n Since before sink 1 we have that the minimum cost violation is equal to 1 Pruning can be po tentially done only for signature variables having more than one value In our example this corre sponds to variables Vo and V5 So we evaluate the four quantities Ming min 0 1 2 1 Ming min 0 1 2 1 Min min min 3 0 1 1 1 1 2 2 Ming min min 3 0 1 0 2 1 If max cost is equal to 1 we can remove value 0 from V5 The corresponding arcs are depicted with a thick line in Fig 7 6 Conclusion and Perspectives The automaton description introduced in this article can be seen as a restricted program ming language This language is used for writing down a constraint checker which ver ifies whether a ground instance of a constraint is satisfied or not This checker allows pruning the variables of a non ground instance of a constraint by simulating all poten tial executions of the corresponding program according to the current domain of the variables of the relevant constraint This simulation is achieved by encoding all poten tial executions of the automaton as a conjunction of signature and transition constraints and by letting the usual constraint propagation deducing all the relevant information We want to stress the key points and the different perspectives of this approach Within the context of global constraints it was implicitly assumed that providing a constraint checker is a much easier task than com
25. er to maintain arc consistency 40 30 E 25 20 built in 0 5 10 15 20 25 30 35 40 automaton 40 between 35 30 built in 154 s Eo nd i 0 Laat t 0 5 10 15 20 25 30 35 40 automaton 40 lex lesseq 35 L 30 25 20 built in 154 10 Dou E bei pt bE 0 basti 0 5 10 15 20 25 30 35 40 automaton Fig 4 Scatter plots for finding all solutions to random instances automaton reformulation vs decomposition to built ins Table 1 Time in milliseconds for finding A the first solution of BIBD instances using built in vs simulated lt jex BCS denotes time spent for breaking column symmetries with respect to the first column BCS corresponds to the time spent in the built in lt 1ex constraint and B all solutions to a single built in vs simulated e constraint A Problem Built in Simulated lt jcx m Built in lt 1ex Simulated lt 1ex 6 190 ao Unary constraints specifying a domain like in 32 or not in 33 Channeling constraints like domain constraint 34 Counting constraints for constraining the number of occurrences of a given set of values like among 14 at least 33 atmost 33 or count 32 Sliding sequence constraints like change 35 longest change or smooth 15 Longest change size vars ctr restricts the variable
26. h is o acyclic and if the constraint network is pair wise consistent the filtering is complete for our global constraint A solution to reach global consistency on the network representing our global con straint is therefore to maintain pairwise consistency In fact if constraints share no more than one variable pairwise consistency is nothing more than arc consistency 23 So pairwise consistency has to be enforced only on pairs of constraints sharing more than one variable and only the transition constraints are therefore concerned In the worst case pairwise consistency will have to consider all the possible tuples of values for the set of shared variables So the pairs of constraints must not share too many variables if we do not want the filtering to become prohibitive Among the 39 constraints studied in 24 seven among atleast atmost count counts differ from atleast k pos and sliding card skipO0 require only one counter two group and group skip isolated item need two counters and max index requires three counters When the automaton involves only one counter consecutive transition constraints share two variables The sweep algorithm presented in 28 can be used to enforce pairwise consistency on each pair of transition constraints sharing two variables Indeed the sweep algorithm on two constraints C and C will forbid the tuples for the variables shared by C and C that cannot be extended on both C and C To summarize
27. ial Intelligence 135 199 234 2002 B Boigelot and P Wolper Representing arithmetic constraints with finite automata An overview In Peter J Stuckey editor ICLP 2002 Int Conf on Logic Programming volume 2401 of LNCS pages 1 19 Springer Verlag 2002 G Pesant A regular language membership constraint for sequence of variables In Workshop on Modelling and Reformulation Constraint Satisfaction Problems pages 110 119 2003 T Petit J C R gin and C Bessi re Specific filtering algorithms for over constrained prob lems In T Walsh editor Principles and Practice of Constraint Programming CP 2001 volume 2239 of LNCS pages 451 463 Springer Verlag 2001 M Milano Constraint and integer programming Kluwer Academic Publishers 2004 ISBN 1 4020 7583 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 24 28 29 30 31 P Van Hentenryck and J P Carillon Generality vs specificity an experience with AI and OR techniques In National Conference on Artificial Intelligence AAAI 88 1988 N Beldiceanu Pruning for the minimum constraint family and for the number of distinct values constraint family In T Walsh editor CP 2001 Int Conf on Principles and Practice of Constraint Programming volume 2239 of LNCS pages 211 224 Springer Verlag 2001 S Bourdais P Galinier and G Pesant HIBISCUS A constraint programming application
28. ing up with a filtering algorithm It was also commonly admitted that the design of filtering algorithms is a difficult task which involves creativity and which cannot be automatized We have shown that this is not the case any more if one can afford to provide a constraint checker Non determinism has played a key role by augmenting programming languages with backtracking facilities 39 which was the origin of logic programming Non determinism also has a key role to play in the systematic design of filtering algo rithms finding a filtering algorithm can be seen as the task of executing in a non deterministic way the deterministic program corresponding to a constraint checker and to extract the relevant information that is common to all execution paths This can indeed be achieved by using constraint programming A natural continuation would be to extend the automaton description in order to get closer to a classical imperative programming language This would allow the direct of available checkers in order to systematically get a automaton reformulation Other structural conditions on the signature and transition constraints could be iden tified to guarantee arc consistency for the original global constraint An extension of our approach may give a systematic way to get an algorithm not necessarily polynomial for decision problems for which one can provide a poly nomial certificate From 40 the decision version of every problem in NP can b
29. n automaton reformulation for C by decomposing it into a conjunction of Pe constraints threading the state and counter variables through the conjunction In addition to this we need the signature constraints Vc S A 0 lt i lt m that relate each signature variables S to the variables of its corresponding signature argument A Filtering for the constraint C is provided by the conjunction of all signature and transitions constraints s being the start state and t being the end state Vc So Ao Sels Ko So Qi K1 We S1 A1 c Qi K1 1 Q2 K2 d Ve Sm 1 Am 1 c Qm 1 Em ijSm i Qm Km A Pe Qm Km t Km41 A couple of examples will help clarify this idea In these examples the relation defined by extension is depicted in a compact form as a decision tree Note that the automaton decision tree automaton decision tree Fig 2 Automata and decision trees for A lt jex and B among decision tree needs to correctly handle the case when the terminal state has already been reached Example 2 Consider a X X1 Yy constraint over vectors of length n First we need a signature constraint W lt relating each pair of arguments z i y i to a signature variable This can be done as follows V Si xli yli 2 lt yli amp Si 1 x i yi e S 2 A x i gt yfi amp S 3 The automaton of Xie and the decision tree corresponding to the tr
30. nizing the set of solutions associated with a global constraint Section 3 shows how to come up with an automaton reformulation which exploits the previously introduced automaton Sec tion 4 describes typical applications of this technique Finally for a restricted class of automata Section 5 provides a filtering algorithm for the relaxed case 2 Description of the Automaton Used for Checking Ground Instances We first discuss the main issues behind the task of selecting what kind of automaton to consider for concisely expressing the set of solutions associated with a global con straint We consider global constraints for which any ground instance can be checked in linear time by scanning once through their variables without using any data struc ture In order to concretely illustrate this point we first select a set of global constraints and write down a checker for each of them Observe that a constraint like for in stance the cycle n 1 2 z constraint which enforces that a permutation 21 29 m has n cycles does not belong to this class since it requires to jump from one position to another position of the sequence x1 2 m Finally we give for each checker a sketch of the corresponding automaton Based on these observations we define the type of automaton we will use 2 4 Selecting an Appropriate Description As we previously said we focus on those global constraints that can be checked by scanning once thr
31. nsition constraints see Fig 3 It has two particular properties there is no cycle in the corresponding dual graph 19 and for any pair of constraints the two sets of involved variables share at most one variable Such a hypergraph is so called Berge acyclic 21 Berge acyclic constraint networks were proved to be solvable polynomially by achiev Se S Q Qa t Fig 3 Constraint hypergraph of the conjunction of transition and signature constraints in the case of disjoint Signature Arg sets The i th Signature Arg set A is denoted by X Yi ing arc consistency 22 23 Therefore if all signature and transition constraints main tain arc consistency then we obtain a complete filtering for our global constraint Among the 39 constraints studied in 24 eight between between_exactly one global contiguity lex different lex lesseq pattern two quad are in contact and two quad do not overlap have an automaton leading to a Berge acyclic hypergraph With counters If there are counters some pairs of constraints share more than one variable So the hypergraph is not Berge acyclic and the filtering performed may be no longer optimal However achieving pairwise consistency on some pairs of constraints leads to a complete filtering To prove this we will use the following well know theorem in database systems Definition 1 25 A constraint network N X D C is pai
32. nt work of Pesant 6 also uses a finite automaton for representing the solution set In this context it provides a filtering algorithm which maintains arc consistency This article focuses on those global constraints that can be checked by scanning once through their variables without using any extra data structure As a second step toward a methodology for semi automatic development of filtering algorithms we in troduce a new approach which only requires defining a finite automaton that checks a ground instance We extend traditional finite automata in order not to be limited only to regular expressions Our first contribution is to show how to reduce the automaton associated with a global constraint to a conjunction of signature and transition con straints We characterize some restrictions on the signature and transition constraints under which the filtering induced by this reduction maintains arc consistency and apply this new methodology to the following problems The design of automaton reformulations for a fairly large set of global constraints The design of automaton reformulations for handling the conjunction of several global constraints The design of constraints between two sequences of variables While all previous related work see Vempaty Amilhastre et al and Pesant relies on simple automata and uses an ad hoc filtering algorithm our approach is based on au tomata with counters and reformulation into constraints
33. orces the variables of vars to take more than a single value sliding_card_skip0O enforces that each maximum non zero subsequence of consecutive variables of vars contain at least atleast and at most atmost values from the set of values values 4 2 Automaton Reformulation for a Conjunction of Global Constraints Another typical use of our new methodology is to come up with an automaton re formulation for the conjunction of several global constraints This is usually difficult since it implies analyzing a lot of special cases showing up from the interaction of the different considered constraints We illustrate this point on the conjunction of the Mar between a a b l and the exact ly_one 2 values constraints for which we come up with an automaton reformulation which maintains arc consistency The between constraint holds iff lt jex x and z lt jex 6 while the exact 1ly_one con straint holds if exactly one component of takes its value in the set of values values The left hand part of Fig 5 depicts the two automata A and A respectively as sociated with the bet ween and the exact 1y one constraints while the right hand part gives the automaton As associated with the conjunction of these two constraints Aa corresponds to the product of A and A2 States of As are labeled by the two states of A and A they were issued Transitions of A3 are labeled by the end symbol or by a conjunction of elementary conditions where ea
34. orithm for handling constraint relaxation under the assumption that we don t use any counter in our automaton It can be seen as a general ization of the algorithm used for the regular constraint 6 Definition 3 The violation cost of a global constraint is the minimum number of sub sets of its signature argument for which it is necessary to change at least one variable in order to get back to a solution When these subsets form a partition over the variables of the constraint and when they consist of a single element this cost is in fact the minimum number of variables to unassign in order to get back to a solution As in 7 we add a cost variable cost as an extra argument of the constraint Our filtering algorithm first evaluates the minimum cost value Min Then according to max cost it prunes values that cannot belong to a solution Example 5 Consider the constraint global contiguity Vo Vi V2 V3 Va Vs Ve with the following current domains for variables V 0 1 1 1 0 1 0 1 1 The constraint is violated because there are necessarily at least two distinct sequences of con secutive 1 To get back to a state that can lead to a solution it is enough to turn the fourth value to 1 One can deduce Min 1 Consider now the relaxed form soft global contiguity Vo Vi V2 V3 Va Vs Ve cost and assume max cost 1 The filtering algorithm should remove value 0 from V5 Indeed selecting value 0 for variable
35. ough their variables This is for instance the case of element 9 minimum 10 pattern 11 global_contiguity 12 lexicographic ordering 13 among 14 and inflexion 15 Since they illustrate key points needed for characterizing the set of solutions associated with a global constraint our discussion will be based on the last four constraints for which we now recall the defini tion The g1obal contiguity vars constraint enforces for the sequence of 0 1 variables vars to have at most one group of consecutive 1 For instance the con straint global contiguity 0 1 1 0 holds since we have only one group of consecutive 1 The lexicographic ordering constraint X lt jcx y over two vectors of variables 7 z9 t amp 1 and y yo yn 1 holds iff n 0 or zo lt yo or zo Yo and 21 uris o1 tex yi sey Un 1 The among nvar vars values constraint restricts the number of variables of the sequence of variables vars that take their value from a given set values to be equal to the variable nvar For instance among 3 4 5 5 4 1 1 5 8 holds since ex actly 3 values of the sequence 45541 are in 1 5 8 The inflexion ninf vars constraint enforces the number of inflexions of the sequence of variables vars to be equal to the variable ninf An inflexion is described by one of the following patterns a strict increase followed by a strict decrease or conversely a strict decrease followed by a stri
36. ransitions now correspond to a condi tion e g xfi yli x i lt y i between two variables of the lt jex constraint Observe that the among nvar vars values constraint involves a variable nvar whose value is computed from a given collection of variables vars The checker de picted by part C1 of Fig 1 counts the number of variables of vars 0 vars n 1 that take their value from values For this purpose it uses a counter c which is eventually tested against the value of nvar This convinced us to allow the use of counters in an automaton Each counter has an initial value which can be updated while triggering certain transitions The final state of an automaton can enforce a variable of the constraint to be equal to a given counter Part C2 of Fig 1 describes the automaton corresponding to the code given in part C1 of the same figure The automaton uses the counter c initially set to 0 and takes as input the sequence vars 0 vars n 1 It triggers a transition for each variable of this sequence and increments c when the corresponding variable takes its value in values The final state returns a success when the value of c is equal to nvar At this point we want to stress the following fact It would have been possible to use an automaton that avoids the use of counters However this automaton would depend on the ef fective value of the parameter nvar In addition it would require more states than the au
37. rwise consistent if and only if VC C Ci 0 and VC C C Cils Cils where s is the set of variables shared by C and C and Ci is the projection of C on s Definition 2 26 An edge in the dual graph of a constraint network is redundant if its variables are shared by every edge along an alternative path between the two end points The subgraph resulting from the removal of the redundant edges of the dual graph is called a join graph A hypergraph has a join tree if its join graph is a tree Theorem 1 25 A database scheme is a acyclic 27 if and only if its hypergraph has join tree Theorem 2 25 Any pairwise consistent database over an a acyclic database scheme is globally consistent To each constraint corresponds a node in the dual graph and if two constraints have a nonempty set S of shared variables then there is an edge labelled S between their corresponding nodes in the dual graph The dual graph is also called intersection graph in data base theory 20 If we translate these theorems we obtain the following corollary on constraint net works Corollary 1 f a constraint hypergraph has a join tree then any pairwise consistent constraint network having this constraint hypergraph is globally consistent In the automata we consider here there are no signature constraints sharing a vari able So the dual graph of the constraint hypergraph is a tree and the hypergraph has a join tree Therefore the hypergrap
38. size to the maximum number of consecutive variables of vars for which the binary constraint ctr holds Variations around the element constraint 9 like element_greatereg 36 lement_lesseq 36 or element_sparse 33 Variations around the maximum constraint 10 like max_index vars index max_index enforces the variable index to be equal to one of the positions of variables corresponding to the maximum value of the variables of vars Constraints on words like global_contiguity 12 group 33 group _skip_isolated_item 15 or pattern 11 Constraints between vectors of variables like between 1 Xie 13 lex different or differ_from_at_least_k_pos Given two vectors xX and y which have the same number of components the constraints lex different Z y and differ from at least k pos k y re spectively enforce the vectors X and jj to differ from at least 1 and k components Constraints between n dimensional boxes like two_quad_are_in_contact 33 or two quad do not overlap 37 Constraints on the shape of a sequence of variables like inflexion 15 top 38 or valley 38 Various constraints like in same partition vari varo partitions not all equal vars orsliding card skipO atleast atmost vars values in same partition enforces variables var and var to be respectively as signed to two values that both belong to a same sublist of values of partitions not all equal enf
39. tomaton of part C2 of Fig 1 This is typically a problem if we want to have a fixed number of states in order to save memory as well as time As the among constraint the inflexion ninf vars constraint involves a variable ninf whose value is computed from a given sequence of variables vars 0 vars n 1 Therefore the checker depicted in part D1 of Fig 1 also uses a counter c for counting the number of inflexions and compares its final value to the ninf parameter This program is represented by the automaton depicted Within the corresponding automata depicted by parts A2 B2 C2 and D2 of Fig 1 we assume that firing a transition increments from 1 the counter i by part D2 of Fig 1 It takes as input the sequence of pairs vars 0 vars 1 vars 1 vars 2 vars n 2 vars n 1 and triggers a transition for each pair Observe that a given variable may occur in more than one pair Each transition compares the respective values of two consecutive variables of vars 0 n 1 and increments the counter c when a new inflexion is detected The final state returns a success when the value of c is equal to ninf Synthesizing all the observations we got from these examples leads to the following remarks and definitions for a given global constraint C For a given state if no transition can be triggered this indicates that the constraint C does not hold Since all transitions starting from
40. ue is an integer giving the value of the counter in the initial state of A and Final Variable gives the variable that should be unified with the value of the counter in the final state of A States is the list of states of A where each state has the form source id sink id or node id id is a unique identifier associated with each state Finally source id and sink id respectively denote the initial and the final state of A Transitions is the list of transitions of A Each transition t has the form arc id label id2 or arc idy label ida counters id and id respectively cor respond to the state just before and just after t while label depicts the value that the signature variable should have in order to trigger t When used counters gives for each counter of Counters its value after firing the corresponding transition This value is specified by an arithmetic expression involving counters constants as well as usual arithmetic functions such as min or max The order used in the counters list is identical to the order used in Counters Example 1 As an illustrative example we give the description of the automaton associated with the inflexion ninf vars constraint We have Signature So 1 4 2 SignatureDomain 0 2 SignatureArg vars 0 vars 1 vars n 2 vars n 1 Counters t c 0 ninf States source s node i node j sink t Transitions arc s 1
41. which transition to trigger next seemed to be good enough Many global constraints involve a variable whose value is computed from a given collection of variables This convinced us to allow the final state of an automaton to optionally return a result In practice this result corresponds to the value of a counter of the automaton in the final state 2 2 Defining an Automaton An automaton A of a constraint C is defined by a sextuple Signature SignatureD omain Signature Arg Counters States Transitions where Signature is the sequence of variables So Sm 1 corresponding to the signa ture of the constraint C SignatureD omain is an interval which defines the range of possible values of the variables of Signature Signature Arg is the signature argument A A4 1 of the constraint C The link between the variables of A and the variable S 0 lt i m is done by writing down the signature constraint Vc 5 A in such a way that arc consistency is maintained In our context this is done by using standard features of the CLP FD solver of SICStus Prolog 16 such as arithmetic constraints between two variables propositional combinators or the global constraints programming interface Counters is the possibly empty list of all counters used in the automaton A Each counter is described by a term t Counter InitialValue FinalVariable where Counter is a symbolic name representing the counter Initial Val
42. xity of the pruning rely on the filtering performed by the solver 3 3 Performance It is reasonable to ask the question whether the automaton reformulation described herein performs anywhere near the performance delivered by a specific implementa tion of a given constraint To this end we have compared a version of the Balanced Incomplete Block Design problem 31 prob028 that uses a built in Xe constraint to break column symmetries with a version using our filtering based on a finite automaton for the same constraint In a second experiment we measured the time to find all solu tions to a single lt jex constraint The experiments were run in SICStus Prolog 3 11 on a 600MHz Pentium III The results are shown in Table 1 A third experiment was designed to measure the overhead of an automaton reformu lation wrt decomposing into built in constraints To this end we produced random in stances of the following constraints studied in 24 among between lex lesseq These constraints were chosen because their automata formulations maintain the same consistency as their decomposed formulations that is they perform exactly the same domain filtering Hence comparing the time it takes to compute all solutions should give an accurate measurement of the overhead among is not a built in constraint it can be decomposed into a number of reified membership constraints and a sum con straint It is worth noting that its automaton uses a counter between
Download Pdf Manuals
Related Search