Does a global constraint cover the entire model?

Not necessarily. It applies to the variables in its specified scope.

Can it be equivalent to several binary constraints?

Yes. AllDifferent is logically equivalent to pairwise inequalities on its variables, although propagation strength can differ.

Does stronger propagation guarantee a faster solve?

No. It may reduce search but costs computation, so the overall tradeoff depends on the problem and implementation.

AI Glossary / Graphs and symbolic AI / Intermediate

Global constraint

Definition

A global constraint is a constraint that expresses a structured relationship over a collection of variables, often with a specialized method for propagating its consequences. A familiar example is AllDifferent, which requires every variable in a specified collection to take a different value. Global constraints are useful in constraint programming because they preserve a recognizable pattern that a solver can exploit.

What it means

The word “global” does not mean that the constraint necessarily mentions every variable in the model. It refers to a relation considered across its whole scope, rather than only as separate small interactions. An AllDifferent constraint might cover the variables for one row of a puzzle while many other variables remain outside its scope.
Some global constraints have equivalent decompositions into simpler constraints. The solutions may be identical, yet propagation can differ because a specialized algorithm reasons about the combined structure. That distinction separates what a constraint means from how effectively a solver uses it during search.

How it works

Declare the participating variables and their current domains, then post the global relation. A propagator examines those domains and removes values that cannot participate in a satisfying assignment according to its supported consistency level. Reduced domains may trigger other propagators, so deductions can spread through the model.
AllDifferent can use matching-based reasoning or other filtering methods. Other global constraints describe resource capacities, occurrences of values, or sequence patterns. Not every implementation provides the strongest possible filtering, and stronger filtering may cost more time. The chosen solver and propagation setting therefore matter alongside the mathematical relation.

Three practical examples

A puzzle model uses AllDifferent to prevent repeated digits within a selected row, column, or region.
A scheduling model uses a cumulative resource constraint to keep overlapping tasks within a capacity limit.
An assignment model limits how many variables may take each value through a global cardinality constraint.

Think of it this way

Think of checking a whole seating chart to ensure that nobody has been assigned the same seat. Looking at the arrangement together can reveal shortages that isolated comparisons miss. The analogy is limited because a solver reasons over sets of possible assignments, not just one completed chart, and its deductions depend on the implemented propagation algorithm.

Worked example

Let X and Y each have domain {1, 2}, while Z has domain {1, 2, 3}. Require AllDifferent(X, Y, Z). X and Y must occupy the two values 1 and 2 in some order. Therefore Z must be 3.
If the relation is decomposed into X ≠ Y, X ≠ Z, and Y ≠ Z, enforcing ordinary arc consistency on each binary inequality alone need not remove 1 or 2 from Z. For Z = 1, each separate inequality can find support by choosing its other variable as 2, but those separate supports cannot both satisfy X ≠ Y simultaneously.
A sufficiently strong AllDifferent propagator considers the combined restriction and removes the unsupported values. Both formulations still describe the same complete solutions: (X, Y, Z) can be (1, 2, 3) or (2, 1, 3). The difference is what can be deduced before branching.

Illustrative case study

In a fictional allocation exercise, the Cedar team gives three demo tasks distinct session slots. Two tasks can use only slots 1 or 2; the third can also use slot 3. The team first encodes separate pairwise inequalities and later uses an AllDifferent constraint.
It compares the domains after propagation rather than claiming that the second model represents a different scheduling rule. With suitable filtering, the third task is fixed to slot 3 immediately. The invented case demonstrates stronger inference from structure; it does not establish a universal runtime advantage for every solver or larger scheduling model.

Common misconceptions and mistakes

A global constraint is not a command to optimize a global objective. It specifies allowed combinations; an objective, if present, chooses among feasible solutions. Global also does not mean that the constraint must be expensive or that a decomposition is always inappropriate.
Avoid assuming that posting AllDifferent guarantees a particular consistency level. Solver options and domain representations may change the propagation used. Also distinguish an empty domain, which proves failure of the current branch, from nonempty domains, which do not by themselves prove that all model constraints can be satisfied together.

Business use

Global constraints give teams a concise language for common planning and allocation requirements. They can make the model easier to inspect and expose structure useful to the solver. This matters when a policy such as “all selected identifiers must be distinct” should be represented directly.
When comparing implementations, check the semantics, supported variable types, and propagation behavior. Test boundary cases such as too few available values or a resource capacity exceeded by overlapping tasks. Performance should be measured on representative instances rather than inferred solely from the presence of a global constraint.

Check your understanding

Why must Z equal 3 when X and Y have domains {1, 2} and all three variables must differ?

Answer: X and Y consume the only two values available to them, namely 1 and 2. Z cannot reuse either value and therefore must take its remaining value 3.

Related terms

Constraint satisfaction
Domain
Constraint propagation
AllDifferent
arc consistency
global cardinality
cumulative constraint
matching

Learn next

Learn next about propagation strength. Add a fourth variable W with domain {1, 2, 3} to the same AllDifferent relation. Explain why no assignment exists, then compare this combined shortage with the supports visible to isolated pairwise inequalities.

Domain

Sources

Choco-solver official integer-constraint documentation: https://choco-solver.org/docs/modeling/intconstraints/ Choco-solver original constraint and propagator tutorial: https://choco-solver.org/tutos/constraints/

Previous: Global calibration Next: Global costmap