Is propagation the same as optimization?

No. It removes impossible possibilities; an optimization procedure additionally seeks the best feasible result under an objective.

Does the order of updates matter?

It can affect intermediate states and efficiency. Properties of the propagators determine the eventual fixpoint behavior.

Can propagation solve a problem without branching?

Sometimes. Other models leave multiple choices or hidden conflicts and require additional search or stronger reasoning.

AI Glossary / Graphs and symbolic AI / Intermediate

Bounds propagation

Definition

Bounds propagation is the repeated tightening of variables' lower and upper limits using constraints. When one bound changes, that information can narrow the bounds of other variables. Constraint solvers use this process to remove impossible values, reveal contradictions, and reduce the amount of search needed before selecting a complete solution.

What it means

Imagine a schedule containing several tasks with uncertain start times. Learning that one task cannot finish before noon may force another task to start later. That later start can affect a third task. Bounds propagation carries these implications through the model without immediately trying every possible schedule.
The result is generally a smaller set of possibilities, not a finished answer. A bound says that values outside it have been excluded by sound reasoning. Values inside it may still fail once several requirements are considered together. The strength of the deductions depends on the constraints, the propagators, and the chosen mathematical domain.

How it works

Each variable begins with a domain or interval. A propagator applies a constraint to those current bounds and computes justified tighter bounds. For an equality x + y = 10, knowing y lies between 3 and 6 implies that x must lie between 4 and 7, before considering any other restriction.
When a bound changes, affected propagators are scheduled again. This repeats until no scheduled propagator can tighten the domains further, or a domain becomes empty and failure is detected. The stable condition is a fixpoint of those propagators. It need not represent every consequence of the model, and some propagation procedures do not achieve the strongest possible bounds consistency.

Three practical examples

A timetable solver pushes a successor task's earliest start later after a predecessor's minimum duration increases.
A resource planner lowers the maximum allocation to one activity when another activity receives a higher minimum allocation under a shared limit.
A product configurator detects that a required minimum output exceeds the maximum achievable output from the remaining component ranges.

Think of it this way

Think of a chain of adjustable fences: moving one fence inward can force neighboring fences to move too. Eventually the local adjustments stop. The analogy captures repeated tightening, but it does not prove that the enclosed space contains a valid complete solution. Numerical constraints can interact in ways that simple local adjustments do not expose.

Worked example

Let integer variables x, y, and z initially range from 0 through 10. Require x + y = 10, y + z = 8, and z at least 6. First tighten z to [6, 10]. Because y cannot be negative, y + z = 8 also gives z at most 8. Thus z becomes [6, 8] and y becomes [0, 2].
Now x + y = 10 forces x into [8, 10]. The current ranges are x in [8, 10], y in [0, 2], and z in [6, 8]. They are not independent choices: x = 8, y = 0, z = 6 lies inside the ranges but violates both equalities. A consistent choice is x = 8, y = 2, z = 6. If a new requirement x at most 7 is added, its intersection with [8, 10] is empty, proving this model infeasible. The example shows both useful narrowing and the need to respect relationships after propagation.

Illustrative case study

At fictional Maple Manufacturing, planners model production quantities with shared capacity limits. Updating a minimum order quantity triggers new upper bounds for other orders. The planning screen explains which capacity rule caused each narrowed range, while leaving final quantity selection to the solver and planner.
When propagation reveals an empty range, the team investigates the conflicting requirements instead of inventing a quantity outside the model. When propagation merely stops, it proceeds with search. This fictional case distinguishes a detected contradiction from an unresolved planning problem; no measured operational result is claimed.

Common misconceptions and mistakes

A fixpoint does not prove feasibility. It only means the active propagation rules cannot currently remove more values. Conversely, sound propagation that empties a domain does establish a contradiction within the modeled assumptions.
Bounds propagation differs from backpropagation in neural networks: it reasons about permitted variable values, not derivatives of a training loss. It also differs from choosing a value during search; propagation derives consequences, while branching introduces alternatives. Finally, numerical rounding matters. Integer bounds and floating-point intervals require appropriate rounding so that a purported tightening does not accidentally discard valid solutions.

Business use

Bounds propagation is useful when businesses need rapid feedback as constraints change. A scheduling or allocation tool can reveal that a request narrows the available choices, even before it computes a complete plan. The practical question is whether the model captures the relevant rules and whether each deduction is sound. Teams should label remaining ranges accurately and retain explanations for contradictions, especially when users need to revise competing requirements.

Check your understanding

After propagation, x is in [8, 10] and y is in [0, 2] with x + y = 10. Can x = 8 and y = 0 be selected independently?

Answer: No. Their sum is 8, so the pair violates the retained constraint.

Related terms

Constraint propagation
bounds consistency
domain filtering
fixpoint
finite-domain solver
interval arithmetic
backtracking

Learn next

Work through a small chain of sum and precedence constraints by hand, recording the reason for each tightened endpoint. After reaching a fixpoint, test a combination inside the remaining ranges. This makes the difference between surviving values and a jointly feasible assignment concrete.

Precedence constraints

Sources

Sources: John Hooker, original CP Summer School tutorial, bounds propagation and its limits: https://johnhooker.tepper.cmu.edu/summerSchool2011.pdf . SICStus Prolog, official CLPFD Glossary, propagation and propagators: https://sicstus.sics.se/sicstus/docs/4.10.0/html/sicstus/CLPFD-Glossary.html .

Previous: Bounds consistent Next: Boustrophedon cell decomposition