Automatic Construction of
Constraint Propagators

Arnaud Lallouet

Editor: Eric Monfroy

The PDF version of this article can be found here.

The design of a constraint solver is certainly a complex task involving the combination of good search algorithms and efficient constraint propagation. The behavior of propagation functions for n-ary constraints rely usually on specialized graph algorithms which depend on the nature of the constraint and the level of consistency to be enforced. The design of an efficient algorithm usually requires a lot of efforts from the developer.

This has motivated a line of work which aims at automatically finding constraint propagators by using Machine Learning techniques. This only requires a specification of the constraint expressed either by a table or by a (logic) program. The advantages range from fast prototyping of global constraints to efficient handling of table constraints. These latter constraints are usually very irregular and never reused: giving them a specialized propagator would not be worth the effort. Usually, automatically constructed propagators do not enforce a consistency as strong as specifically tailored algorithms but the difference tend to reduce and the efforts consented to build the propagator are by far much lower.

After recalling the properties of propagators, we present a survey of some existing approaches which aim to build automatically such functions.

Propagators

Let us consider a set of variables and their finite domains. A constraint on a subset of variables restricts the values theses variables can take simultaneously to a certain subset called the solutions of the constraints. A Constraint Satisfaction Problem (or CSP) is a set of constraints. A solution of a CSP is an affectation of the variables such that all constraints are satisfied. In order to limit memory consumption, it is convenient to use as main representation only the domains of the variables. This defines a search state as the Cartesian product of the variables' domains.

A consistency is a desirable property which holds for certain states. For example, a state is arc-consistent if each value of the domain of each variable has a support, i.e. for each constraint in which this variable is involved, there exists a solution compatible with the other variables's current possible values. Weaker levels of consistency are also possible, for example by enforcing the property on the bounds of the domain.

A constraint propagator is a reduction function for the variables of a constraint. For each variable, it aims at pruning unsupported bounds or domain values. They define the exact level of consistency which will be enforced for their own constraint. Then constraint propagators are executed up to reach their greatest common fixpoint. A propagator cannot be any function. The following properties are required in order to ensure confluence, termination, correctness and completeness of the propagation mechanism:

• monotony: a value pruned in a state is also pruned in any of its subset.
• contractance: a propagator cannot add new values in a domain.
• correctness: a propagator cannot prune a value involved in a solution.
• singleton completeness: a propagator represents its constraint. Hence it should be a satisfiability test for singleton states.

A Quick Survey

Automatic solver design has been investigated by several approaches, showing the power of the technique, but also some of its limitations. We present in the following a few approaches in a chronological order:

· Generalized Propagation and Propia: proposed in the early 90' by Le Provost and Wallace [12], this work has set many of the ideas in the context of Constraint Logic Programming. The basic idea is to make a Prolog predicate behave like a constraint. Hence, instead of branching on disjunctions like it does for an ordinary Prolog definition, the system computes a correct over-approximation of the set of solutions as a set of constraints in a given language and adds these constraints to the current store.
This technique allows to derive an operator from the predicate's definition by a special kind of evaluation called topological branch and bound. The operator is dynamically built each time the constraint is woken up, which happens in a standard way whenever one of the constraint's variable is further constrained. Constraints implied by the current constraint store and the constraint are then computed and added to the store.
The Propia system also proposes to transform a set of Prolog facts into a table constraint (implemented with the element global constraint) in order to give it a propagation behavior.

Except for Prolog facts/table constraints, the difference between Propia and subsequent systems is mainly to allow the operators to be computed prior to execution. One of the problems is to find a representation for propagator functions.

· Equality/Membership rules: Apt and Monfroy [4] have proposed to analyze a constraint defined by a table and to build automatically a set of rules for all possible propagation events. They propose to use two rule languages. The first kind of rule is called equality rule. For a constraint c(X,Y,Z), it has the form X=a, Y=b -> Z=c. The second kind of rule is called membership rule and has the form X in A, Y in B -> Z in C. Only the second kind of rule is powerful enough to represent arc-consistency.
In contrast with Propia, the set of rules is computed off-line from the constraint's definition, by a simulation of any context in which the constraint may react to. Minimal, non-redundant and correct rules are recorded as the solver for the constraint.
The original algorithm uses a simple enumeration of all rules and contexts in which each rule may be used. Its high complexity restricts its use to what the authors call small finite domains, 2 or 3 values in practice.
· PropMiner: as an extension of the previous work, the Propminer system [3] provides more flexibility in the specification of the rule language. The idea is to provide a language for the left-hand side and one for the right-hand side and let the system enumerate all possibilities as above. For example, if constraints on both sides are equality between a variable and a constant, then we get equality rules.
The PropMiner system allows to use CHRs [8], which gives flexibility and allows the constructed solver to be used within a Prolog supporting CHRs. The rule enumeration strategy is improved over the preceding algorithm. Practice suggest that the number of rules can increase tremendously when dealing with large arities/domain sizes. But, as in the Propia system, powerful deductions that go beyond arc-consistency can be done, like the inference of an equality between two variables and not only between a variable and a constant.
The authors have also investigated using Prolog predicates as specification [2] and the optimization of the produced solver by syntactic transformations of CHRs [1].
· Solar: this system aims at using Machine Learning techniques for solver construction. It explores the use of indexicals to represent propagators of constraints defined by a table. It proposes to build an approximation of bound-consistency by adjusting the parameters of a function template [7]. The candidate function is compared to the expected consistency by counting the number of reduced values along the search space. The closest correct approximation in average is found and used as a propagator.
The relation represented by the propagator can be slightly different from the original relation. Correctness is ensured along the whole process, but not completeness and it can happen that the propagator accepts a non-solution tuple. The exact solutions are then repaired by using a delayed table constraint [10].
Two extensions have been done in order to ensure arc-consistency for specific constraints. By using clustering techniques, constraints with packed solutions can be given an intermediate consistency called multibound-consistency [9]. Also, constraints with either dense or sparse hyperplanes orthogonal to a domain value can be exploited efficiently by choosing a subset of (short) propagation rules [13]. Compared to previous approaches, the Solar system can handle much larger domain size/arity.
Home page for the Solar project can be found at:
http://www.univ-orleans.fr/lifo/Members/lallouet/research/solar.html

The last approach is not fully automatic since it requires the user to provide an algorithm for satisfiability instead of just a specification of the constraint.

· Automaton: the idea of [5] is to ask the user to provide an automaton in which the transitions are labeled by conditions on variables. A word on variable subsets is then parsed by the automaton and the output tells whether the variable assignment is a solution or not. Then, under some syntactic restrictive conditions, it is possible to enforce arc-consistency by a specific evaluation on the unfolded the automaton.
The main area of use is to express global constraints since many useful ones can be checked by this kind of automaton.

Future Issues

For fully automatic methods, there is a compromise between the quality of the consistency and the scalability of the approach: full arc-consistency may be obtained but only for small arities and/or domain size. If bound-consistency or an approximation of arc-consistency is acceptable, then larger problems may be processed. A challenge would be to have both.

Further on, the use of Machine Learning techniques to provide propagators to classical constraints suggest to extend the notion of constraint to partially defined constraints or open constraints. Such constraints are defined by a set of examples and counter-examples, while most of the remaining tuples are unknown. One may want to acquire such constraints either as a CSP [6], by a classifier [14] or directly by a propagator [11]. Applications are:

• user interaction in programming environment: a novice user could specify some examples of the problem he/she has in mind and let the system find a possible consistent set of constraints.
• reformulation: automatic addition of redundant constraints.
• optimization in a learned concept: the open constraint may be used to ïnvent" an object, while the optimization part allows to select the best invented proposition.

Open constraints can extend the modeling capabilities of Constraint Programming towards incompletely defined constraints. This field has not been taken into account so far or has been rejected outside the constraint model. Anyone who is interested in this topic may contact the author:

http://www.univ-orleans.fr/lifo/Members/lallouet/

Bibliography

[1]

Slim Abdennadher and Christophe Rigotti. Using confluence to generate rule-based constraint solvers. In Principles and practice of declarative programming, pages 127-135, Florence, Italy, September 5-7 2001. ACM.

[2]

Slim Abdennadher and Christophe Rigotti. Automatic generation of rule-based solvers for intensionally defined constraints. International Journal on Artificial Intelligence Tools, 11(2):283-302, 2002.

[3]

Slim Abdennadher and Christophe Rigotti. Automatic generation of rule-based constraint solvers over finite domains. Transaction on Computational Logic, 5(2), 2004.

[4]

K.R. Apt and E. Monfroy. Automatic generation of constraint propagation algorithms for small finite domains. In Joxan Jaffar, editor, International Conference on Principles and Practice of Constraint Programming, volume 1713 of LNCS, pages 58-72, Alexandria, Virginia, USA, 1999. Springer.

[5]

Nicolas Beldiceanu, Mats Carlsson, and Thierry Petit. Deriving filtering algorithms from constraint checkers. In Mark Wallace, editor, Principles and Practice of Constraint Programming, volume 3258 of LNCS, pages 107-122, Toronto, Canada, October 1 2004. Springer.

[6]

Christian Bessière, Rémi Coletta, Eugene C. Freuder, and Barry O'Sullivan. Leveraging the learning power of examples in automated constraint acquisition. In Mark Wallace, editor, Principles and Practice of Constraint Programming, volume 3258 of LNCS, pages 123-137, Toronto, Canada, 2004. Springer.

[7]

Thi-Bich-Hanh Dao, Arnaud Lallouet, Andrei Legtchenko, and Lionel Martin. Indexical-based solver learning. In Pascal van Hentenryck, editor, International Conference on Principles and Practice of Constraint Programming, volume 2470 of LNCS, pages 541-555, Ithaca, NY, USA, Sept. 7 - 13 2002. Springer.

[8]

Thom Frühwirth. Theory and practice of Constraint Handling Rules. Journal of Logic Programming, 37(1-3):95-138, 1998.

[9]

Arnaud Lallouet, Andreï Legtchenko, Thi-Bich-Hanh Dao, and AbdelAli Ed-Dbali. Intermediate (learned) consistencies. In Francesca Rossi, editor, International Conference on Principles and Practice of Constraint Programming, volume 2833 of LNCS, pages 889-893, Kinsale, County Cork, Ireland, 2003. Springer.

[10]

Arnaud Lallouet, Andreï Legtchenko, Thi-Bich-Hanh Dao, and AbdelAli Ed-Dbali. Learning approximate consistencies. In Francesca Rossi Péter Szeredi Krzysztof R. Apt, François Fages and József Váncza, editors, Joint Annual Workshop of the ERCIM Working Group on Constraints and the CoLogNET area on Constraint and Logic Programming, pages 285-298, MTA SZTAKI, Budapest, Hungary, 2003.

[11]

Arnaud Lallouet, Andreï Legtchenko, Eric Monfroy, and AbdelAli Ed-Dbali. Solver learning for predicting changes in dynamic constraint satisfaction problems. In Ken Brown Chris Beck and Gérard Verfaillie, editors, Changes'04, International Workshop on Constraint Solving under Change and Uncertainty, Toronto, CA, 2004.

[12]

Thierry Le Provost and Mark Wallace. Generalized constraint propagation over the CLP Scheme. Journal of Logic Programming, 16:319-359, 1993.

[13]

Andreï Legtchenko, Arnaud Lallouet, and AbdelAli Ed-Dbali. Intermediate consistencies by delaying expensive propagators. In Valerie Barr and Zdravko Markov, editors, Flairs'04, International Florida Artificial Intelligence Conference, South Beach Miami, FL, USA, 2004. AAAI Press.

[14]

F. Rossi and A. Sperduti. Acquiring both constraint and solution preferences in interactive constraint system. Constraints, 9(4), 2004.