Interval Contractor¶

A box-to-box operator that narrows an interval search region without removing any point satisfying its declared target constraints.

Version: v2 · 2026-10-03 · History
Domain-specific #: 13343
Domain group: Formal Sciences
Origin domain: Mathematics
Subdomains: Validated Numerics, Numerical Constraint Processing → Mathematics
Aliases: Contractor for Constraints, Interval Constraint Contractor

Core Idea¶

An interval contractor is a rule for safely narrowing a box of possible real-valued inputs. Relative to a declared target set \(X\subseteq\mathbb R^n\), it sends every axis-aligned interval box \(B\) to another box \(C(B)\) such that

\[C(B)\subseteq B\quad\text{and}\quad C(B)\cap X=B\cap X.\]

The first condition is contractance: the output never extends outside the original search region. The second is feasible-point preservation: every point satisfying the target constraints that was in the input remains in the output. Thus the operator may discard regions proved inconsistent with \(X\), but it cannot discard a valid solution. Chabert and Jaulin give this classical constraint-associated definition as the pointwise requirement that every removed point fails the constraint.^[1]

The distinction between sound and strong narrowing matters. A contractor is sound even if it returns \(B\) unchanged. It need not return the smallest box containing \(B\cap X\), and its output may include points outside \(X\). Narrowing quality depends on the particular construction and the information available about the constraint. Nor is a contractor itself a complete equation solver: solvers can compose contractors, repeat them, split surviving boxes and apply stopping or existence tests.^[1]^[2]

The name has a definitional nuance. In their broader contractor-programming formalism, Chabert and Jaulin add pointwise consistency and a continuity condition to the contraction axiom, permitting contractors not directly tied to a single constraint. This entry analyzes the classical contractor for a declared feasible set or constraint, where the two displayed relations specify the target-preserving identity. It does not silently assert that every general contractor in their expanded formalism has a unique given \(X\).^[1]

Structural Signature¶

Sig role-phrases: target feasible set \(X\) → input interval box \(B\) → contracting box operator \(C\) → preservation of \(B\cap X\) → optional composition/search.

Target feasible set. \(X\) identifies which points matter—often the solutions of \(f(x)=0\), the solutions of inequalities, or an intersection of such constraints. If \(X\) is changed, the same numerical map may cease to be sound for the new problem. The target is constitutive for the set-associated definition.^[1]
Input interval box. \(B=[x_1]\times\cdots\times[x_n]\) represents a rectangular domain of candidates. The operator acts on a box, not on one guessed point or an arbitrary non-box region. This choice enables interval arithmetic and box-based search but may enclose irrelevant points when \(X\) is curved or disconnected.^[1]
Contracting output. \(C(B)\) is again a box contained in \(B\). Returning a wider enclosure may be safe for another purpose but fails the contractor's contractance test.^[1]
Feasible-point preservation. \(C(B)\cap X=B\cap X\) is the non-loss invariant. Any removed point must be provably outside \(X\); otherwise a true solution could disappear and later search would be invalid. Keeping extra infeasible points is permissible, though it may be computationally costly.^[1]
Construction and composition. Forward–backward evaluation, interval Newton variants and half-space contractors are ways to obtain a useful \(C\). Composition or propagation combines them, often to handle several conditions. These are common implementations and uses, not additional axioms of every contractor.^[1]^[2]

A proposed map is identified by testing both constitutive relations for the declared \(X\) and every admissible box, not merely by observing that one example box became smaller. A one-box demonstration cannot by itself prove that no solution is ever lost.

What It Is Not¶

It is not interval arithmetic alone. Interval arithmetic encloses results of arithmetic expressions over interval inputs. A forward evaluation \(F(B)\) may bound \(f(B)\), but without returning a sub-box of the original variables and preserving their target-feasible points, it is not yet an interval contractor. Interval arithmetic is often used inside a contractor.^[2]

It is not an arbitrary shrinking heuristic. A rule that discards inconvenient or low-scoring candidates may shrink a box, but if it loses even one point of \(X\), it fails the preservation invariant for that target. The guarantee is mathematical and conditional on correct constraints, interval enclosures and implementation—not a visual impression that the surviving box looks plausible.^[1]

It is not necessarily a minimal hull or an inner approximation. \(C(B)\) is an outer box for feasible points in \(B\): all such points are retained, while infeasible points may remain. The smallest box containing \(B\cap X\) would be the strongest possible box-shaped contraction, but most algorithms seek a computationally cheaper sound enclosure.^[1]

It is not identical to branch-and-prune, set estimation, or constraint propagation. Those are broader workflows or purposes. A branch-and-prune solver invokes a contractor, then may bisect a residual box and repeat. Set estimation asks which states or parameters are compatible with bounded observations. Propagation orchestrates multiple contractors. None of these is the definition of one box-to-box operator.^[1]^[2]

Scope of Application¶

The literal home is numerical constraint solving over real variables represented by interval boxes. Equations such as \(x_1=\exp(x_2)\) and systems of inequalities supply a feasible set \(X\); a contractor narrows a candidate box while preserving the solutions. The paper's equation example is a direct construction, while IBEX's planar polygon example combines contractors for half-spaces.^[1]^[2]

Contractors also serve as pruning components in interval-based root finding and set inversion. Chabert and Jaulin show a root-finder that contracts a box, discards an empty result, and bisects surviving boxes that are still too wide. This solver may produce a subpaving of small boxes around roots; a contractor by itself makes only the local safe-narrowing promise. Termination precision, proof of existence or uniqueness, and the representation of disconnected solution components are separate questions.^[1]

Bounded-error robot localization is another interval-analysis habitat: a candidate pose must be compatible with measurement intervals and a model. Kieffer and colleagues report a set-based localization method that can retain multiple pose regions when measurements do not distinguish them. This shows why preservation of every feasible candidate matters in application, but their whole localization system is not being equated with one contractor here.^[3]

Clarity¶

The word “contract” alone is ambiguous: does it mean only that a region became smaller, or that it became smaller without deleting solutions? The two equations in Core Idea make the distinction testable. A proposed interval filter with \(C(B)\subseteq B\) but \(C(B)\cap X\ne B\cap X\) is not sound for \(X\).^[1]

It also clarifies the direction of approximation. The output is an outer enclosure of the feasible points within the input box, not an assertion that all output points are feasible. If \(C(B)=B\), the operator may have learned nothing about that box yet can still be valid. If \(C(B)=\varnothing\), soundness certifies that \(B\cap X=\varnothing\) under the stated model and arithmetic assumptions.^[1]

The distinction between a contractor and a solver prevents another inference error. A box that cannot be narrowed may still contain both feasible and infeasible points. Bisection, another contractor, an existence theorem or a stopping policy may be needed; lack of further local contraction is not itself proof that the box is entirely feasible.^[1]^[2]

Manages Complexity¶

A nonlinear feasible set can be curved, disconnected or difficult to express exactly. A contractor compresses one part of that geometric question into a cheap box-level test: which coordinate ranges can be eliminated while retaining every feasible point? This lets a larger algorithm reason with tractable rectangular states rather than individual continuum points.^[1]

The invariant is compositional. If \(C_1\) and \(C_2\) both preserve the same target set \(X\), applying one after the other still cannot remove an \(X\)-point. In practice contractors can be built for separate constraints and combined so that the current box is tightened repeatedly. IBEX's polygon construction uses half-space contractors in precisely this modular way.^[2]

Compression has a cost. A box must cover spaces between separated feasible components; a weak contractor can leave broad ranges for later splitting. More elaborate propagation may tighten these bounds but requires additional calculations, and interval dependency can make a forward–backward pass less accurate when variables recur in an expression.^[2]

Abstract Reasoning¶

Start by declaring \(X\) and \(B\). Then ask whether each proposed coordinate removal is justified by a constraint: if a point in the removed strip could satisfy \(X\), the operator is unsound. This is a stronger reasoning step than testing a routine on sample points, since the claim quantifies over all target-feasible points in every admissible input box.^[1]

Next separate soundness from tightness. Soundness asks whether \(B\cap X\) survives unchanged. Tightness asks how much infeasible volume or coordinate width remains. One may improve tightness by deriving a stronger contractor, composing several contractors, or bisecting the box, but none of those choices can relax the non-loss condition without changing the problem.^[1]^[2]

Finally, interpret outputs at the right strength. An empty contracted box proves absence of feasible points in the original box, conditional on a sound implementation and a correct model. A nonempty output is merely a region that may contain feasible points. It is not a root existence proof, unique solution, minimal hull, or guaranteed inner approximation.^[1]

Knowledge Transfer¶

Within validated numerical computation, the same contractor test transfers from a single nonlinear equation to a conjunction of half-space inequalities: both declare an \(X\), accept interval boxes, shrink them, and preserve every \(X\)-point. What changes is the construction: inverse interval operations fit the exponential equation, while IBEX composes forward–backward contractors for the polygon's inequalities.^[1]^[2]

The local non-loss guarantee can also be used within root finding and bounded-error state estimation, provided each application's constraints and error bounds are carried into \(X\). The mathematical guarantee transfers; the conclusion that a localization is accurate or a root exists does not follow from contraction alone. Those stronger conclusions require application-specific premises and additional algorithms or theorems.^[1]^[3]

Outside numerical box methods, “filtering without discarding true answers” resembles conservative search pruning. That is an analogy to a wider structural concern, not literal transfer of the named interval contractor: the box input, target-set equation and interval-validity obligations do not automatically exist in another substrate.

Examples¶

Nonlinear equation on a positive box¶

Chabert and Jaulin give \(f(x_1,x_2)=x_1-\exp(x_2)=0\). On a box \(B=[x_1]\times[x_2]\) with positive first-coordinate interval, one sound contractor intersects \([x_1]\) with \(\exp([x_2])\) and \([x_2]\) with \(\log([x_1])\). For instance, start with \([x_1]=[2,3]\) and \([x_2]=[0,2]\). The second interval narrows to \([\log 2,\log 3]\) while the first remains \([2,3]\). Every pair on the curve \(x_1=\exp(x_2)\) inside the original box remains. This is an illustrative interval calculation from the paper's construction, not a claim that the resulting rectangle contains only points on the curve.^[1]

Mapped back: target feasible set = the exponential curve; input interval box = \([2,3]\times[0,2]\); contracting output = \([2,3]\times[\log2,\log3]\); feasible-point preservation = no original pair satisfying the equation is excluded; construction and composition = direct inverse interval intersections, with no bisection or multi-constraint composition required.

A planar polygon from half-spaces¶

The IBEX project documents constructing a regular polygon by several linear half-space constraints. It builds a forward–backward contractor for each inequality and composes the contractors for the polygon's interior. A rectangular candidate region can be narrowed against each half-space in turn. The resulting box still contains every point in the initial rectangle that satisfies all polygon inequalities, although its corners may remain outside the polygon; the construction is a box filter, not an exact polygon representation.^[2]

Mapped back: target feasible set = the intersection of polygon half-spaces; input interval box = a planar candidate rectangle; contracting output = a possibly smaller rectangle after composition; feasible-point preservation = every polygon point originally in the rectangle survives; construction and composition = individual forward–backward inequality contractors combined by the documented composition operator.

Boundary: interval evaluation alone¶

Evaluating an interval extension of a function over \(B\) can produce an enclosure of function values. Without returning a sub-box of the original variables and establishing preservation of \(B\cap X\) for a specified target \(X\), that calculation is a building block rather than a contractor.

Structural Tensions¶

T1 — Sound preservation versus aggressive narrowing. A stronger reduction may leave fewer boxes for later search, but removing a single feasible point destroys the defining guarantee. A safe yet weak operator may leave large infeasible portions of the input box, imposing later computational work. Neither maximum shrinkage nor maximum conservatism is free. Diagnostic: For the stated \(X\), is every removed point demonstrably infeasible, and how much irrelevant region remains after sound contraction?^[1]

T2 — More local propagation versus solver cost. Composing or revisiting contractors may achieve a tighter box before bisection, but each pass costs computation; a cheap local pass can leave more residual boxes for later subdivision. IBEX notes that variable repetition weakens forward–backward narrowing and that propagation schedules repeated calls selectively. Diagnostic: For these constraints and this search, does the extra safe narrowing reduce total work enough to justify its cost, or should the solver split earlier?^[2]

Structural–Framed Character¶

Interval Contractor is predominantly structural. Its defining relation is a pair of box/set inclusions, and soundness can be checked mathematically without agreeing on a social norm. Evaluative weight: “better” can mean tighter or cheaper, but the identity itself requires only non-loss and contractance; performance preferences are external. Human-practice dependence: choices of constraints, tolerances and software implementations affect applications, yet the two constitutive equations do not depend on an institution's approval. Institutional origin: numerical-analysis and constraint-programming communities named and developed the method, but disciplinary authority is not what makes a map a contractor. Vocabulary travel: “contractor” has many unrelated ordinary meanings; the interval-specific definition travels only where boxes and feasible sets are actually typed. Import versus recognition: a new implementation is recognized by proving the invariants, not by labeling any narrowing routine a contractor.^[1]^[2]

The portable skeleton is conservative elimination under an invariant, but that phrase alone lacks the interval-box mathematics that individuates this entry. Its character: a structurally crisp, domain-specific numerical operator whose application range is broad within validated constraint computation but whose literal tests do not transfer intact to unrelated domains.

Structural Core vs. Domain Accent¶

The admitted general parent is live Mathematical Operator: a typed action on mathematical objects. Interval Contractor is a strict specialization because its objects are interval boxes and its action must obey both \(C(B)\subseteq B\) and \(C(B)\cap X=B\cap X\). The more portable idea “remove candidates while preserving every valid answer” may be a future-prime question, not an admitted extra parent; live Pruning has an overgeneration/use-signal story and does not state this proof-driven feasible-set invariant.^[1]

The domain accent is not just naming. Interval geometry, the declared target set, exact set intersection and sound interval implementation determine what counts as evidence of preservation. Without those, “contracting” could mean ordinary data compression, a heuristic filter or geometric shrinkage. Such analogies can inspire design but do not make the named contractor substrate-independent. Its domain-specific status remains even when the same box method is applied to optimization, localization or nonlinear root finding.^[1]^[3]

This entry is a kind of Mathematical Operator.

Mathematical Operator (live domain-specific; the broader abstraction): the contractor is a typed box-to-box map with the additional target-preserving contraction laws.
Function/Mapping (live prime; inherited through Mathematical Operator): the broad input-to-output structure alone says nothing about sound elimination.
Branch and Bound (live prime; related workflow): interval branch-and-prune calls a contractor before possibly splitting boxes; the contractor is not the complete search pattern.
Set Estimation (live domain-specific; related application): compatible state sets can be enclosed and narrowed using contractors, but the estimation problem and the operator are different identities.
Interval Arithmetic (staged domain-specific; related building block): supplies safe interval evaluation, which a forward–backward contractor may use, but does not by itself narrow the variable box with target-set preservation.

Only the Mathematical Operator edge is proposed in structured frontmatter. These other relations are catalog comparisons, not additional asserted parents.

Relationships to Other Abstractions¶

Current abstraction Interval Contractor Domain-specific

Parents (1) — more general patterns this builds on

Interval Contractor is a kind of Mathematical Operator Domain-specific

An interval contractor is a mathematical operator specialized to solution-preserving box contraction.

Hierarchy path (1) — routes to 1 parentless root

Interval Contractor → Mathematical Operator → Function (Mapping)

Neighborhood in Abstraction Space¶

Interval Contractor sits in a sparse region of the domain-specific corpus (75^th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Unclustered & Miscellaneous (2551 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-08

Not to Be Confused With¶

Interval arithmetic transforms operand intervals into safe output intervals; interval contraction narrows candidate input boxes relative to a target set. Constraint propagation schedules possibly many local contractors, while one contractor can stand alone. Branch-and-prune adds box splitting and termination rules. Subpaving is a collection of boxes approximating a set, often produced after repeated contraction and splitting. Set estimation asks which hidden states fit bounded data, and an interval contractor may be one tool for that task. A contraction mapping in fixed-point analysis has a metric distance-reduction property; that is not the same as the box-inclusion and target-preservation conditions here.^[1]^[2]

References¶

[1] Gilles Chabert and Luc Jaulin, “Contractor Programming,” Artificial Intelligence 173 (2009), 1079–1100, especially §1.1, Example 1; §1.2; and §3.2. Author-hosted paper. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n ↩o ↩p ↩q ↩r ↩s ↩t ↩u ↩v ↩w ↩x ↩y ↩z ↩27 ↩28

[2] IBEX team, “Contractors,” IBEX 2.9 project documentation, especially Forward-Backward, Intersection/Union/Composition, polygon example, and Propagation. Official documentation. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n

[3] Michel Kieffer, Luc Jaulin, Éric Walter and Dominique Meizel, “Localisation et suivi robustes d’un robot mobile grâce à l’analyse par intervalles,” Traitement du Signal 17 (2000), 207–219, abstract and §§3–5. Publisher page and article. registry ↩a ↩b ↩c