Abstract
Numeric Constraint Satisfaction Problems (NCSPs) present unique challenges due to the continuous nature of their domains. Traditional discrete consistency techniques often fail or become computationally prohibitive in these spaces. This paper introduces arc B-consistency and 3-B-consistency, two formalisms that adapt interval propagation to provide efficient pruning of the search space by focusing on variable bounds rather than individual values.
Introduction
Constraint Satisfaction Problems (CSPs) are a cornerstone of artificial intelligence, typically defined over finite, discrete sets. However, many real-world problems in engineering and physical modeling are naturally expressed as Numeric CSPs (NCSPs), where variables represent real numbers or large integers.
The transition from discrete to numeric domains introduces a "combinatorial explosion." In a continuous domain, the number of potential values is infinite. Even when discretized using floating-point approximations, the density of values makes standard arc consistency—which tracks individual consistent values—computationally infeasible. A particular challenge arises with disjunctive constraints, where a single variable might require tracking a multitude of disconnected intervals, leading to a representation explosion.
The B-Consistency Framework
Prior to this work, "interval propagation" was a heuristic used in various constraint logic programming systems like CHIP and BNR-Prolog. This paper provides the first formal definition of consistency for these techniques and a rigorous complexity analysis. The core idea is to treat domains as intervals and focus on their bounds (the "B" in B-consistency).
Arc B-consistency
Arc B-consistency formalizes the standard interval propagation technique. Instead of verifying every value within a domain, it ensures that for each bound of a variable's interval, there exists a set of values in the other variables' intervals that satisfy the constraint. By maintaining domains as single intervals, this method preserves "convexity" and avoids the exponential growth of interval representations.
3-B-consistency
For problems where arc B-consistency is insufficient, the author proposes 3-B-consistency. This is a stronger form of consistency that employs a "refutation" approach. The algorithm temporarily narrows a variable's domain to a small sub-interval near one of its bounds. If arc B-consistency then proves this sub-interval is inconsistent with the rest of the system, that bound can be permanently tightened. This process is analogous to path consistency in discrete CSPs but is optimized for interval bounds.
Precision and Interval Arithmetic
To make these techniques practical, two key components are introduced:
- Precision Tuning ($w$): A "width" parameter allows the filtering process to terminate once interval bounds are within a specified distance. This provides a direct mechanism to trade off computation time for result precision.
- Interval Arithmetic: To account for the inherent inaccuracies of floating-point computations, the algorithms rely on interval arithmetic. This ensures that the "true" mathematical solution is never pruned due to rounding errors.
Experimental Evaluation
The techniques were evaluated using synthetic problems and complex non-linear systems.
As shown in Figure 1, synthetic NCSPs ($P_1, P_2, P_3$) were used to demonstrate the limitations of simple arc consistency and the effectiveness of 3-B-consistency. In these examples, constraints are defined by systems of linear equations and inequalities. While arc B-consistency provides a baseline for pruning, 3-B-consistency can often narrow domains significantly further, sometimes to a single point, without requiring explicit domain splitting (branching).
The methods were also tested on a large-scale non-linear system consisting of 22 variables and 22 constraints, including trigonometric functions. Experimental results on an IBM 3090 confirmed that while the theoretical worst-case complexity is high, the algorithms typically perform near their lower bounds in practice.
Insights and Limitations
A key insight of this work is that for many numeric problems, global consistency is not required; tightening the "box" containing the solutions is often sufficient for practical applications. Furthermore, for "non-disjunctive" constraints (simple continuous functions), arc B-consistency is proven to be as powerful as standard arc consistency while being significantly more efficient.
However, limitations remain. Like all local consistency techniques, these methods do not guarantee that a solution exists within the final intervals. Additionally, the "multi-occurrence" problem—where a variable appears multiple times in a single constraint—can lead to interval over-estimation, a classic challenge in interval arithmetic.
Conclusion
By providing a formal framework and complexity analysis for interval propagation, this paper moved numeric constraint solving from a collection of heuristics to a field of rigorous algorithms with predictable performance. These techniques remain foundational to modern solvers used in engineering and optimization.
Summary updated