This article presents a model and implementation techniques for speeding up constraint propagation. Three fundamental approaches to improving constraint propagation based on propagators as implementations of constraints are explored: keeping track of which propagators are at fixpoint, choosing which propagator to apply next, and how to combine several propagators for the same constraint. We show how idempotence reasoning and events help track fixpoints more accurately. We improve these methods by using them dynamically (taking into account current variable domains to improve accuracy). We define priority-based approaches to choosing a next propagator and show that dynamic priorities can improve propagation. We illustrate that the use of multiple propagators for the same constraint can be advantageous with priorities, and introduce staged propagators that combine the effects of multiple propagators with priorities for greater efficiency. • 2:3 solution to the CSP. The other subproblem has x 1 ∈ {2}, x 2 ∈ {2} and x 3 ∈ {1, 2}, and leads to another solution. As can be seen from the example, finite domain constraint programming interleaves propagation with search. In this paper we investigate how to make a propagation engine as efficient as possible. There are two important decisions the engine must make: which propagators should execute, and in which order should they execute. To make constraint propagation efficient, it is clear that the engine needs to take the following issues into account: avoid unnecessary propagator execution, restrict propagation to relevant variables, and choose the cheapest possible method for propagation. In this article we show how propagation can be sped up if the engine takes these issues into account. The contributions of the article are as follows: -We give a formal definition of propagation systems including fixpoint and event-based optimizations used in current propagation systems. -We extend event-based propagation systems to use dynamically changing event sets. -We introduce multiple propagators and staged propagators for a single constraint for use with propagation queues with priority. -We give experimental results that clarify the impact of many choices in implementing propagation engines: including idempotence reasoning, static and dynamic events, basic queuing strategies, priority queues, and staged propagation. Plan of the Article. The next section introduces propagation-based constraint solving, followed by a model for constraint propagation systems in Section 3. Section 4 presents how to optimize propagation by taking idempotence into account, while Section 5 explores the use of event sets. Which propagator should be executed next is discussed in Section 6, while combination strategies of multiple propagators for the same constraint is discussed in Section 7. Experiments for each feature are included in the relevant section, and a summary is given in Section 8. Section 9 concludes. This section defines our terminology for the basic components of a constraint propagation engine. In this paper, we restrict ourselves to finite domain integer constraint solving. Almost all the discussion applies to other forms of finite domain constraint solving such as for sets and multisets. A domain D is a complete mapping from a fixed (finite) set of variables V to finite sets of integers. A false domain D is a domain with D(x) = ∅ for some x ∈ V. A variable x ∈ V is fixed by a domain D, if |D(x)| = 1. The intersection of domains D 1 and D 2 , denoted D 1 D 2 , is defined by the domain A domain D 1 is stronger than a domain D 2 , written D 1 D 2 , if D 1 (x) ⊆ D 2 (x) for all x ∈ V. A domain D 1 is stronger than (equal to) a domain D 2 w.r.t. variables A range is a contiguous set of integers; we use range notation [l . . u] to denote the range {d ∈ Z | l ≤ d ≤ u} when l and u are integers. A domain is a range domain if D(x) is a range for all x. Let D = range(D) be the smallest range domain containing D, that is, the unique domain We shall be interested in the notion of an initial domain, which we denote D init . The initial domain gives the initial values possible for each variable. It allows us to restrict attention to domains D such that D D init . Constraints. An integer valuation θ is a mapping of variables to integer values, written {x 1 → d 1 , . . . , x n → d n }. We extend the valuation θ to map expressions and constraints involving the variables in the natural way. Let vars be the function that returns the set of variables appearing in a valuation. We define a valuation θ to be an element of a domain D, written θ ∈ D, if θ(x i ) ∈ D(x i ) for all x i ∈ vars(θ ). The infimum and supremum of an expression e with respect to a domain D are defined as inf D e = inf{θ (e) | θ ∈ D} and sup D e = sup{θ (e) | θ ∈ D}. We can map a valuation θ to a domain D θ as follows
Several possibilities can be considered to implement constraint propagation when multiple propagators are available REF .
Efficient constraint propagation engines
TOPL
Computer Science