Improved bounds on the complexity of kB-consistency

1 Introduction

Consistency algorithms are polynomial techniques which aim at struggling against the combinatorial explosion of bruteforce search by reducing the search space. Among them, strong consistencies [Freuder, 1978] denote generic algorithms which can be tuned to enforce arbitrary intermediate levels of consistency. One of the most (if not the most) promising strong consistency techniques is the class of ✂ ✄ - consistencies, where ✂ may vary from ✓ to a maximum value corresponding to global consistency.

✂ ✄ -consistencywas introduced in [Lhomme, 1993] as a response to the problem called early quiescence [Davis, 1987]: when applied to non-trivial, real-valued problems, filtering techniques adapted from arc-consistency do not reduce the search space enough in practice, and stronger consistencies are thus needed to limit the size of the search tree. The basic idea is that given a solver of level ✂ ✔ ✖ , each possible value of the variables can be enumerated; if the ✂ ✔ ✖ solver proves the inconsistency of the problem obtained when variable ✙ is instantiated to value ✚ , we know that ✚ is not a possible value for ✙ . This method can be applied to both domainbased solvers (by suppressing inconsistent values from domains) and interval-based solvers (by tightening bounds).

The domain-consistency obtained, called singletonconsistency has been emphasized as one of the most efficient techniques for hard finite-domain problems [Debruyne and Bessi`ere, 1997]. This paper deals with the interval-consistency obtained, called ✂ ✄ -consistency. ✂ ✄ -consistency has been successfully applied to difficult nonlinear problems, such as a challenging transistor design application [Puget and van Hentenryck, 1998]. The important advantage of ✂ ✄ over path-consistency [Montanari, 1974] and its variants [Dechter and van Beek, 1996; Sam-Haroud and Faltings, 1996] is that it does not require the use of the costly multi-dimensional representations of the constraints needed in these methods.

Let ☛ be the number of elements in the widest initial interval, ✎ be the number of variables, and ✠ be the number of constraints; the known bound of time-complexity for computing ✂ ✄ -consistency is ✝ ✞ ✠ ☛ ✜ ✣ ✥ ✎ ✌ ★ ✜ ✣ ✌ ✫ ✑ : ✓ ✄ is computed in ✝ ✞ ✠ ☛ ✑ and each increase in the factor ✂ has a cost of ✝ ✞ ☛ ✎ ✌ ✑ . Our aim is to show that this complexity is overestimated and that the expected optimum is actually ✝ ✞ ✠ ☛ ✜ ✣ ✥ ✎ ✜ ✣ ✌ ✑ . We show that this bound can be approached in the general case and that it can be exactly reached in the especially interesting case of ✆ ✄ .

This result is obtained by a cautious formulation of the algorithm, in which an optimization pointed out by Lhomme and Lebbah [Lebbah, 1999] is integrated. Informally speaking, each time an interval is reduced, the ✂ ✔ ✖ solver performs an incomplete computation. The optimization is to store the result of this computation, so that successive calls to the solver do not need to be restarted from scratch. A dynamic dependency condition is used to determine that some operations can be avoided. We then study the cost of the cumulation of all these incomplete computations to find improved bounds on time complexity.

The outline of this paper is the following: next section introduces the required material and terminology on constraints and solvers. Section 3 introduces interval consistency techniques and in particular ✂ ✄ -consistency. We then define and prove two improvements to a naive algorithm for computing it (Section 4). A theoretical analysis of the resulting algorithm allows us to state the new complexity results in Section 5, while the end of the paper is concerned with conclusions and perspectives.

2 Constraints and Solvers

We note ✴ the domain of computation. ✴ is supposed to be finite and totally ordered: it is thus possible to compute the predecessor and the successor of any element ✚ . This assumption may seem very restrictive, but it corresponds to the usual representation of numbers with computers: in practice, ✴ is either the set of the canonical floating-point intervals or the subset of the integers encoded on a given number of bits.

2.1 Basic terminology

Let ✵ be a finite set of variables. A point ✶ is defined by a coordinate ✶ ✷ on each variable ✙ , i.e., points are mappings from ✵ to ✴ . A constraint ✸ is a set of tuples. For readers more familiar with database-theoretic concepts [Dechter and van Beek, 1996], variables may also be thought of as field names, points as tuples, and constraints as relations or tables. Points may also be seen as logical valuations.

A CSP ✹ is a set of constraints. The set of solutions to ✹ is the set ✺ ✻ ✽ ✞ ✹ ✑ of the points which belong to all its constraints, i.e., ✺ ✻ ✽ ✞ ✹ ✑ ✾ ✿ ✸ ❀ ✸ ❃ ✹ ❅ . The problem of constraint satisfaction is to find (one/all) solution(s) to a CSP. It is a NPcomplete problem in its decisional form.

The cut ❆ ❇ ❉ ❋ ✞ ✸ ✑ of a set of points ✸ is the set containing the points of ✸ whose coordinate on ✙ is ✚ : ❆ ❇ ❉ ❋ ✞ ✸ ✑ ✾ ✿ ✶ ❃ ✸ ❀ ✶ ✷ ✾ ✚ ❅ . It is also referred to as the selection or instantiation operator. Among other properties, this operator is monotonic: ✸ ▼ ✸ a80 ❘ ❆ ❇ ❉ ❋ ✞ ✸ ✑ ▼ ❆ ❇ ❉ ❋ ✞ ✸ a80 ✑ .

Though these definitions are fully general and do not depend on the way constraints are expressed, some points in this paper are concerned with the special case of systems of equations and inequations over ✴ . As an example of such systems, ✿ ✖ ❱ ✙ ❲ ✖ ❱ ❨ ✾ ❬ ❪ ✙ ✾ ❨ ❅ defines the CSP ✹ ✾ ✿ ✸ ✥ ❪ ✸ ✌ ❅ where ✸ ✥ ✾ ✿ ❵ ✙ ❪ ❨ ❪ ❬ ❜ ❀ ✖ ❱ ✙ ❲ ✖ ❱ ❨ ✾ ❬ ❅ and ✸ ✌ ✾ ✿ ❵ ✙ ❪ ❨ ❪ ❬ ❜ ❀ ✙ ✾ ❨ ❅ . A solution is ❵ ✙ ✾ ✓ ❪ ❨ ✾ ✓ ❪ ❬ ✾ ✖ ❜ . The cut ❆ ❡ ❉ ❢ ✞ ✸ ✥ ✑ defines the set ✿ ❵ ✙ ❪ ❨ ❪ ✖ ❜ ❀ ✖ ❱ ✙ ❲ ✖ ❱ ❨ ✾ ✖ ❅ .

Notations: Throughout the text, the considered CSP will be fixed and called ✹ ; consequently we shall omit this parameter in most definitions.

2.2 Interval-consistency

We call search space (✐ ) the set of points among which solutions are searched for. In the interval-consistency framework [Benhamou and Older, 1997], the search space is the cartesian product of intervals associated to every variable. The success of this representation comes from the fact that it is a compact and expressive way to approximate the solutions. We note ✽ ❥ ✷ and ❧ ❥ ✷ the lower and upper bounds of the interval of possible values for variable ✙ . The search space is thus the set containing the points ✶ whose coordinates are inside the bounds (♥ ✙ ❃ ✵ ❪ ✶ ✷ ❃ a114 ✽ ❥ ✷ ❪ ❧ ❥ ✷ a116 ). It is called a box, due to the obvious geometric intuition. When we refer to a bound ❥ ✷ without further detail, it can be indifferently the lower or the upper bound of ✙ .

An intuitive way to reason on bounds is by relating them to the facets of the box. Formally, a facet is the set of points of the box whose coordinate on a given variable is fixed to a bound: it can be written ❆ ❇ ❉ ✉ ❇ ✞ ✐ ✑ for some variable ✙ and some bound ❥ ✷ of ✙ .

Notations: Given a box ✐ , we note ✸ ✻ ✎ ✈ ① ✈ ✶ ② ✎ ✶ ✞ ✐ ✑ the property ✐ ③ ✺ ✻ ✽ ✞ ✹ ✑ ⑤ ✾ ⑥ , which states that ✐ contains a solution.

2.3 Solvers

We define (constraint) solvers as functions which verify the following properties:

Definition 1. [Solver] A solver is a function ⑧ on boxes such that:

Note that we deliberately exclude the case of nonidempotent solvers, which are not relevant here. Solvers are intended to reduce the search space; the key-point is that they are usually integrated within a branch and prune algorithm, which is guaranteed to find the solutions only if the solver does not remove any of them, hence we call this essential property correctness. The opposite property to correctness is completeness, which states the implication ❷ ✸ ✻ ✎ ✈ ① ✈ ✶ ② ✎ ✶ ✞ ✐ ✑ ❘ ⑧ ✞ ✐ ✑ ✾ ⑥ . Complete solvers are able to detect all inconsistencies, but are usually too costly to be considered practically.

3 kB-consistency

The solvers we now consider can be seen as functions which tighten the intervals by modifying each bound in turn; we often refer to this process as facet reduction, meaning that facets are "pushed down". Solvers are defined via local consistency properties, which characterize the facets obtained when the reduction stops. We now define ✂ ✄ -consistency inductively, starting with a basic consistency technique for the case ✂ ✾ ✓ .

3.1 2B-consistency

✓ ✄ -consistency is also called hull-consistency by some authors [Benhamou and Older, 1997]. On finite domains, it is the core of some of the main constraint logic programming solvers [Van Hentenryck et al., 1998; Codognet and Diaz, 1996], and it is often referred to as partial lookahead.

Definition 2. [2B-consistency] A box ✐ is 2B-consistent if for every bound ❥ ✷ we have:

The ✓ ✄ -consistency solver is the function ⑧ ✌ which maps a box ✐ to the greatest ✓ ✄ -consistent box included in ✐ .

This definition means that bounds are reduced until each facet of the box intersects every constraint. It can be proved that ⑧ ✌ is a valid function: the computed greatest box exists and is unique; this result comes frommore general properties of confluence of fixpoint computations [Apt, 1999]. Furthermore, ⑧ ✌ is a valid solver: correctness holds because a value ✚ is suppressed froma variable ✙ if ❹ ✸ ❃ ✹ ❪ ❆ ❇ ❉ ❋ ✞ ✹ ✑ ③ ✸ ✾ ⑥ , so that we have ❷ ✸ ✻ ✎ ✈ ① ✈ ✶ ② ✎ ✶ ✞ ❆ ❇ ❉ ❋ ✞ ✹ ✑ ✑ , which proves that the solver only removes facets which do not contain solutions; idempotence is straightforward and monotonicity comes from the monotonicity of the selection operator.

✓ ✄ -consistency can only be computed for some special constraints called primitive, which correspond to the basic arithmetic relations defined by the language. Solvers like Prolog IV decompose arbitrary constraints (e.g., ✞ ✓ ❲ ✙ ✑ ❻ ❨ ✾ ❬ ) into such primitive constraints ( ✓ ❲ ✙ ✾ ✙ a80 ❪ ✙ a80 ❨ ✾ ❨ a80 ❪ ❨ a80 ✾ ✙ ).

3.2 kB-consistency

The condition that every facet intersects every constraint is a very rough approximation of (global) consistency. ✂ ✄ - consistency relies on the observation that ideally, a facet should be reduced until it contains a solution; since deciding whether a facet contains a solution is itself a constraint satisfaction problem, a solver ⑧ ✜ ✣ ✥ can do for this task.

Definition 3. [kB-consistency] A box ✐ is ✂ ✄ -consistent (for ✂ ❾ ✆ ) if for every bound ❥ ✷ we have:

The ✂ ✄ consistency solver is the function ⑧ ✜ such that the box ⑧ ✜ ✞ ✐ ✑ is the greatest ✂ ✄ -consistent box included in ✐ .

Informally speaking, bounds are reduced until no facet is rejected by the solver ⑧ ✜ ✣ ✥ . This definition is recursive: ✆ ✄ - consistency uses the ✓ ✄ -consistency solver and can in turn be used to define ➀ ✄ -consistency, and so on. Properties of confluence, idempotence and monotonicity hold for ⑧ ✜ . Its correctness is a consequence of the correctness of ⑧ ✜ ✣ ✥ : since ⑧ ✜ ✣ ✥ ✞ ❆ ❇ ❉ ✉ ❇ ✞ ✐ ✑ ✑ ✾ ⑥ implies ❷ ✸ ✻ ✎ ✈ ① ✈ ✶ ② ✎ ✶ ✞ ✹ ✑ , the removed facets do not contain any solution. It is easy to prove that ⑧ ✜ is "stronger" than ⑧ ✜ ✣ ✥ , i.e., that ⑧ ✜ ✞ ✐ ✑ ▼ ⑧ ✜ ✣ ✥ ✞ ✐ ✑ (this is due to the monotonicity of ⑧ ✜ ✣ ✥ ).

Note that the idea of ✂ ✄ -consistency can be customized and that any consistency technique can be used instead of ✓ ✄ - consistency. Some authors have considered the use of Boxconsistency [Puget and van Hentenryck, 1998] or lazy forms of arc-consistency [Debruyne and Bessi`ere, 1997].

4 Algorithms

We now present the algorithms for computing ✂ ✄ - consistency. As far as ✓ ✄ -consistency is concerned, we only sketch the notions required to understand the subsequent proofs, and the reader is referred to [Benhamou and Older, 1997; Lhomme, 1993] for further explanations.

We then give an incremental description of the algorithm for ✂ ✄ -consistency in the general case: starting from a naive algorithm, we successively describe two optimizations used by the experts of this technique and suggested in [Lebbah, 1999] (see also [Delobel, 2000]). The theoretical interest of these improvements shall be studied in the next section.

4.1 Computing 2B-consistency

The algorithm for enforcing ✓ ✄ -consistency is a variant of the seminal propagation algorithm - AC3. It is a "constraintoriented" algorithm, which handles a set of constraints to be considered (generally stored as a queue). It relies on the fact that every constraint ✸ relates a given number of variables - we say that ✸ depends on this variable ✙ , or alternatively that ✸ constrains ✙ . Figure 1 describes the algorithm.

Two points are essential to the complexity study:

1 ➁ := ➂ 2 while ➁ ➃ ➄ ➅ do 3 ➁ := ➁ ➆ ➇ ➉ ➊ % arbitrary choice of ➉ 4 for each variable ➋ constrained by ➉ do 5 reduce ➌ ➍ ➏ while ➑ ❇ ❉ ➒ ✉ ❇ ➓ ➔ → ➣ ➉ ➄ ➅ 6 reduce ↔ ➍ ➏ while ➑ ❇ ❉ ↕ ✉ ❇ ➓ ➔ → ➣ ➉ ➄ ➅ 7 if ➙ ➌ ➍ ➏ ➛ ↔ ➍ ➏ ➜ has been modified then 8 ➁ := ➁ ➝ ➇ ➉ ➞ ➠ ➂ ➢ ➉ ➞ depends on ➋ ➛ ➉ ➞ ➃ ➄ ➉ ➊

• ➦ In the case of numeric constraints, each constraint depends on (at most) ✆ variables;
• ➦ Lines 5 and 6 of the algorithm can be performed in bounded time using interval computations.

4.2 Naive algorithm for kB-consistency

The filtering of a box ✐ by ✂ ✄ -consistency is computed by reducing each of its facets in turn. In the following algorithm (Figure 2) we use the notation reduce ❻ ❻ ❻ while to represent the computation of the new bound. This notation actually represents a loop: while the specified condition does not hold, the bound is iteratively reduced to the next (when reducing a lower bound) or previous (upper bound) element. This loop may indeed be optimized, for instance by trying to remove several values at once, or even by using recursive splitting. Unfortunately, these heuristics do not improve the worst-case complexity: at worst, every value has to be considered in turn to be effectively reduced.

The correctness of this algorithm is straightforward since when the ➳ ➵ ➸ ➺ ➼ loop stops, all the bounds are ✂ ✄ -consistent.

4.3 Storing information

The most obvious drawback of the preceding algorithm is that each time a facet ❆ ❇ ❉ ✉ ❇ ✞ ✐ ✑ is reconsidered, the solver ⑧ ✜ ✣ ✥ is restarted from scratch to reduce it. A more clever approach is to store the result of this reduction, in order to reuse it in the next steps (Figure 3). The notation memorize is a simple assignment, but it is intended to express the fact that the memorized box has already been computed in the previous line.

We use a vector ✠ ② ✠ 1 which associates to every bound the last ➚ non-empty box computed while reducing it. When a bound ❥ ✷ is reconsidered, it is possible to restart the solver from the box ✠ ② ✠ a114 ❥ ✷ a116 ③ ✐ (cf. Line 4), because we have:

Proof. Note that the intersection ✠ ② ✠ a114 ❥ ✷ a116 ③ ✐ is a way to rewrite ✠ ② ✠ a114 ❥ ✷ a116 ③ ❆ ❇ ❉ ✉ ❇ ✞ ✐ ✑ since ✠ ② ✠ a114 ❥ ✷ a116 contains only points with value ❥ ✷ on ✙ . Since ✠ ② ✠ a114 ❥ ✷ a116 ✾ ⑧ ✜ ✣ ✥ ✞ ❆ ❇ ❉ ✉ ❇ ✞ ✐ a80 ✑ ✑ for some ✐ a80 ⑨ ✐ , a direct consequence of monotonicity is that ⑧ ✜ ✣ ✥ ✞ ❆ ❇ ❉ ✉ ❇ ✞ ✐ ✑ ✑ ▼ ✠ ② ✠ a114 ❥ ✷ a116 . We also have ⑧ ✜ ✣ ✥ ✞ ❆ ❇ ❉ ✉ ❇ ✞ ✐ ✑ ✑ ▼ ❆ ❇ ❉ ✉ ❇ ✞ ✐ ✑ (contractance), and thus ⑧ ✜ ✣ ✥ ✞ ❆ ❇ ❉ ✉ ❇ ✞ ✐ ✑ ✑ ▼ ✠ ② ✠ a114 ❥ ✷ a116 ③ ❆ ❇ ❉ ✉ ❇ ✞ ✐ ✑ ✑ . Using monotonicity and idempotence we prove that ⑧ ✜ ✣ ✥ ✞ ❆ ❇ ❉ ✉ ❇ ✞ ✐ ✑ ✑ ▼ ⑧ ✜ ✣ ✥ ✞ ✠ ② ✠ a114 ❥ ✷ a116 ③ ❆ ❇ ❉ ✉ ❇ ✞ ✐ ✑ ✑ ✾ ⑧ ✜ ✣ ✥ ✞ ✠ ② ✠ a114 ❥ ✷ a116 ③ ✐ ✑ . The other inclusion ⑨ is straightforward.

4.4 Avoiding computation

The second optimization relies on the observation that it is not worth recomputing a bound ❥ ✷ if ✠ ② ✠ a114 ❥ ✷ a116 ▼ ✐ , because ✠ ② ✠ a114 ❥ ✷ a116 ③ ✐ is then equal to ✠ ② ✠ a114 ❥ ✷ a116 which is already a fixpoint of the solver ⑧ ✜ ✣ ✥ . In the algorithm of Figure 4, this condition is checked in a naive fashion before each bound reduction:

Figure 5 is an illustration of the preceding considerations: in this figure, bound ❧ ❥ ✷ is reduced but the global box still contains ✠ ② ✠ a114 ✽ ❥ ➬ a116 (= ⑧ ✜ ✣ ✥ ✞ ❆ ➮ ❉ ➒ ✉ ➮ ✞ ✐ a80 ✑ ✑ for some box ✐ a80 ⑨ ✐ ). The re-computation of bound ✽ ❥ ✷ can therefore be avoided.

5 Complexity analysis

This section is concerned with the theoretical study of the algorithms, starting with the special case of ✓ ✄ -consistency. We then study the complexity of the algorithms of Section 4, and point out little improvements needed to compute ✂ ✄ in near-optimal time. As a comparison, we first recall the original complexity results given in [Lhomme, 1993]. As usual in the literature [Mackworth and Freuder, 1985], the complexity of local consistency algorithms is expressed as a function of the following parameters:

1 Technically, bounds may be seen as variables, it is thus legitimate to use their value (c.f. ➑ ❇ ❉ ✉ ❇ ➓ ➔ → ) or to modify them (as in "reduce ➍ ➏ while"). Our use of the notation ➽ ➾ ➽ ➙ ➍ ➏ ➜ is slightly abusive, the intended meaning is that the stored value is associated to the bound, not to its current value.

• ➦ ✎ ✾ ❀ ✵ ❀ the number of variables,
• ➦ ✠ ✾ ❀ ✹ ❀ the number of constraints,
• ➦ ☛ the number of elements in the greatest interval of the box.

In general, it is possible to artificially define as many constraints as is wished on a given number of variables. On the contrary, it is not possible to have ✎ a242 ✆ ✠ (for ternary constraints) unless the absurd case of disconnected constraint graphs is accepted, thus ✎ ✾ ✝ ✞ ✠ ✑ .

5.1 Complexity of 2B-consistency

The complexity of ✓ ✄ -consistency has been determined by [Lhomme, 1993] using an argument inspired from [Mackworth and Freuder, 1985]. We recall this result and give a simpler proof:

Complexity 1. The time-complexity for the algorithm computing ✓ ✄ -consistency (see Figure 1) is ✝ ✞ ✠ ☛ ✑ .

Proof. Between two insertions of a constraint ✸ into the set a244 , the reduction of one of the intervals on which ✸ depends must have occurred. ✸ depends on a bounded number of variables (3 in our case), and each interval may be reduced at most ☛ times. The overall number of insertions of a given constraint into the queue is hence bounded by ✝ ✞ ☛ ✑ , and the number of insertions of the ✠ constraints is ✝ ✞ ✠ ☛ ✑ . Since Lines 5 and 6 of the algorithm require constant time, this gives the complexity.

We also recall the best-case running time: when no reduction is obtained (the box is already ✓ ✄ -Consistent), every constraint is dequeued in time a245 ✞ ✠ ✑ .

5.2 Complexity of the original algorithm

The complexity of the original algorithm for ✂ ✄ -consistency presented in [Lhomme, 1993] is the same as the one of the naive algorithm presented in Figure 2. To show that this algorithm runs in time ✝ ✞ ✠ ☛ ✜ ✣ ✥ ✎ ✌ ★ ✜ ✣ ✌ ✫ ✑ , we just prove the following result:

Complexity 2. The number of calls to the solver ⑧ ✜ ✣ ✥ in the naive ✂ ✄ -consistency algorithm is ✝ ✞ ☛ ✎ ✌ ✑ .

Proof. The worst case is obtained when re-computing all facets a246 (Line 2 of the algorithm of Figure 2) results in a minimal reduction (removal of one element) of only one of the bounds: consequently, ✝ ✞ ✎ ✑ applications of ⑧ ✜ ✣ ✥ are needed to remove one element. Since one interval is associated to each of the ✎ variables, ☛ ✎ elements may be suppressed one after the other in the worst case, hence the overall number of applications of the solver ⑧ ✜ ✣ ✥ is ✝ ✞ ☛ ✎ ✌ ✑ .

Note that this complexity does not seem to be optimal: since we use the solver ⑧ ✜ ✣ ✥ to test each element of every variable, we could expect an optimal algorithm to perform only ✝ ✞ ☛ ✎ ✑ calls to ⑧ ✜ ✣ ✥ . We shall see how this presumably optimal bound can be reached in the case of ✆ ✄ -consistency.

5.3 3B-consistency

We now have all the theoretical elements at hand for a critical study of the algorithm of Figure 4. We first restrict ourselves to the case of ✆ ✄ -consistency, whose expected optimal complexity is ✝ ✞ ✠ ☛ ✌ ✎ ✑ . The algorithmof Figure 4 is not optimal yet for a simple reason: to suppress some value on a given interval, it may be needed to apply several ✓ ✄ -consistencies, each time with cost ✝ ✞ ✠ ✑ . The problem is that ✓ ✄ is run on all constraints in a systematic way, while only the ones which depend on a bound which has been reduced since the last run should be enqueued.

This situation may be avoided with a finer storage of the queues used by ✓ ✄ -consistency (Figure 6): a queue a247 a114 ❥ ✷ a116 is attached to each facet ❥ ✷ , and each time the reduction of a facet stops, the corresponding queue is empty. Only the constraints which effectively have to be reconsidered are enqueued (Line 12). In the following the expression using means that ⑧ ✌ is run with a247 a114 ❥ ✷ a116 as an initial queue instead of the queue containing all the constraints used in Figure 1:

Note that this algorithm is essentially the same as the one of Figure 4 where the test for inclusion in Line 10 and the intersection in Line 11 are applied in an optimized way. These two operations can be especially easily computed since only the interval for the variable ✙ which has effectively been changed has to be checked or reduced.

Complexity 3. The algorithm of Figure 6 is optimal ( ✝ ✞ ✠ ☛ ✌ ✎ ✑ ).

Proof. Several calls to the solver ⑧ ✌ may be required to suppress a value ✚ from a given variable. Throughout these calls, each constraint is taken into account only if one of the variables on which it depends has been reduced (either during the current computation of ✓ ✄ -consistency or between the previous computation and the current one). The cumulated number of constraint insertions into the queue for all the calls related to value ✚ is then bounded by ✝ ✞ ✠ ☛ ✑ . Since ✝ ✞ ☛ ✎ ✑ such values may be suppressed, the global cost is ✝ ✞ ✠ ☛ ✌ ✎ ✑ .

This bound is correct because the number of tests of interval inclusions has been optimized: in the algorithm, ✝ ✞ ✎ ✑ interval inclusions are checked every time one of the ✝ ✞ ☛ ✎ ✑ elements is effectively removed, and the cost of these tests is then ✝ ✞ ☛ ✎ ✌ ✑ . Since ✎ is ✝ ✞ ✠ ✑ , this complexity is less than ✝ ✞ ✠ ☛ ✌ ✎ ✑ .

5.4 Complexity of kB-consistency

We refine the analysis of the complexity of ✂ ✄ -consistency. Figure 7 shows the savings obtained by the memorization presented before. ✐ ✥ is a facet of some box. It is reduced by ✞ ✂ ✔ ✖ ✑ ✄ -consistency in order to show that the corresponding value ✚ is inconsistent. The values suppressed by ✞ ✂ ✔ ✓ ✑ ✄ - consistency appear as tiles on the figure. The second part of the figure shows a case where the search space ✐ a80 has been reduced and the re-computation of ✞ ✂ ✔ ✖ ✑ ✄ -consistency is needed.

✟

✠

Figure 7: Successive reductions of a facet ➑ ❇ ❉ ❋ ➓ ➔ → .

To determine the complexity of ✂ ✄ -consistency, we bound the number of filterings by ✞ ✂ ✔ ✓ ✑ ✄ -consistency (i.e. the tiles). The keypoint is that the algorithm stores the suppressions obtained by ✞ ✂ ✔ ✓ ✑ ✄ , and avoids computing them several times. We have the following result:

Complexity 4. When computing ✂ ✄ -consistency, the number of computations of ✞ ✂ ✔ ✓ ✑ ✄ -consistency is ✝ ✞ ☛ ✌ ✎ ✦ ✑ .

Proof. Consider the computation needed to suppress some value ✚ associated to a variable ✙ ( ✚ may be thought of as the bound ❥ ✷ of the box). ✝ ✞ ☛ ✎ ✑ such values exist. Due to the memorization, it is needed to re-compute the ✞ ✂ ✔ ✖ ✑ ✄ - consistency on the facet ❆ ❇ ❉ ❋ ✞ ✐ ✑ only in the case where one of the values of the corresponding memorized box ( ✠ ② ✠ a114 ❥ ✷ a116 ) has been removed. In the worst case, it may happen that no computation of ✞ ✂ ✔ ✖ ✑ ✄ -consistency reduces the memory; up to ✝ ✞ ☛ ✎ ✑ such computations can thus occur, since ✝ ✞ ☛ ✎ ✑ suppressions of a single value of the memory may occur. Each time, the number of ✞ ✂ ✔ ✓ ✑ ✄ -consistencies that are checked is ✝ ✞ ✎ ✑ (one is run on each facet of ❆ ❇ ❉ ❋ ✞ ✐ ✑ ).

✡

✁

☛

✑

✌

✤

✍

✏

✑

✖

✓

a253

✛

a254

✜

a253

✢

✘

a255

✏

a0

✁

✑

✑

✄

✤

✤

✓

✆

The overall number of ✞ ✂ ✔ ✓ ✑ ✄ -consistencies is bounded by ✝ ✞ ☛ ✌ ✎ ✦ ✑ .

Since the original bound on the number of ✞ ✂ ✔ ✓ ✑ ✄ - consistencies is ✝ ✞ ☛ ✌ ✎ ★ ✑ , we have shown an improvement of the worst-case behaviour. We summarize the results for ✓ ✄ , ✆ ✄ , and stronger consistencies ( ✂ a80 ❾ ✖ ):

6 Conclusion

Investigating several improvements to a basic algorithm for computing ✂ ✄ -consistency, we have designed an optimal algorithmfor ✆ ✄ -consistency, and shown that improvedbounds are reached for higher values of ✂ . Note that the algorithms presented here are very affordable in terms of space complexity: the storage of the boxes needed by the algorithms of Figures 4 and 6 requires space ✝ ✞ ✂ ✎ ✌ ✑ ( ✎ ✌ space is needed to store a box for each facet at each level and no two applications of some solver for the same level of ✂ may coexist). The handling of the queues in the algorithm of Figure 6 requires ✝ ✞ ✎ ✠ ✑ additional space.

In terms of algorithms, our main contribution was to overview and justify theoretically some improvements based on some memorization of computation. Though our purpose was not to discuss the practical relevance of this technique, it actually proves to be effective on our implementation, since it allows saving some percents of the computations of facets. Typical benchmarks show that 5% to 60% of the facet reduction may be avoided while computing ✆ ✄ -consistency. It might be possible to generalize these memorization techniques to each level of ✂ ✄ -consistency, and hence to improve the theoretical time-complexity - to the detriment of spacecomplexity.

Our study of the complexity of interval consistency techniques may be regarded as complementary to the qualitative results which compare the filtering obtained by the algorithms. For instance, it is well-known that ✆ ✄ -consistency allows to compute more precise intervals than Box-consistency [Collavizza et al., 1999], but that it is also a more costly technique. Since the efficiency of constraint solving depends on the compromise between the pruning obtained and the time required to achieve it, an interesting perspective is to study the difference between the two algorithms in terms of theoretical costs.

Note that our study was restricted to the original definition of ✂ ✄ -consistency, and that the alternative definition based on Box-consistency introduced in [Puget and van Hentenryck, 1998] has not been considered. Since Box-consistency is computed in a very similar way to ✓ ✄ , it seems however that little customization of our algorithm is needed to handle this case. A more challenging task would be to determine whether similar optimizations to the ones presented in this paper may be helpful in the combinatorial case, where domains are considered instead of intervals.

Acknowledgements We express our gratitude to Olivier Lhomme for its encouragements and advice.