Can a binary constraint be directional?

Yes. X preceding Y is different from Y preceding X, even if a graph drawing shows one connecting edge.

Is X = Y a binary constraint?

Yes, when X and Y are two distinct variables.

Are binary constraints always easy to solve together?

No. Networks of simple pairwise restrictions can still pose difficult search problems.

AI Glossary / Graphs and symbolic AI / Beginner

Binary constraint

Definition

A binary constraint is a restriction involving exactly two variables in a constraint satisfaction problem. It specifies which pairs of values are allowed. Binary refers to the number of variables involved, not to whether their values are only zero and one.

What it means

Constraint satisfaction describes a problem using variables, their possible values and rules that combinations must obey. A binary constraint links two choices. Two meetings may need different rooms, one task may need to finish before another begins, or two selected components may need compatible connectors.

The possible values can be numbers, labels, dates or objects. A constraint between two room variables with twenty possible rooms each is still binary. Conversely, a rule involving three Boolean variables is not binary merely because every variable has two possible values.

A complete solution assigns every variable a permitted value and satisfies all applicable constraints. Passing one pairwise check says only that the particular relationship is acceptable. It does not prove that the remaining choices can be completed consistently.

Hard constraints rule out combinations. Soft preferences can instead assign costs or desirability scores, but they should be identified separately so users know whether a rule is mandatory.

How it works

A binary constraint can be represented by a table of allowed pairs or by a condition such as X < Y. A constraint graph represents variables as vertices and constrained pairs as edges. The relationship carried by an edge still needs to be specified; the drawing alone does not say whether two values must match or differ.

Solvers use these relationships during search and propagation. If X receives a value, forward checking can remove values of Y that conflict with it. Arc consistency goes further: every remaining value of X must have at least one supporting value in Y for the relevant constraint, and vice versa when both directed checks are enforced.

Supports are local. Different neighbors may support a value using mutually incompatible assignments, so arc consistency is not a general guarantee of a complete solution.

Some higher-arity constraints can be represented using binary constraints, sometimes with auxiliary variables. The representation can change propagation strength and model size. A global all-different constraint and a collection of pairwise inequalities have the same allowed complete assignments, but a dedicated global propagator may detect restrictions that separate pairwise checks miss.

Three practical examples

A meeting scheduler prevents two overlapping sessions from using the same room through a constraint between their room assignments.
A product configurator allows a processor and motherboard pair only when their socket types are compatible.
A workshop planner requires the start of a finishing task to follow the start of a preparation task by at least its fixed duration.

Think of it this way

Think of a compatibility chart with one product choice along the rows and another along the columns. A marked cell means that particular pair is allowed.

The analogy is limited to a two-choice relationship. Several individually acceptable charts can still leave no combination that satisfies the whole collection.

Worked example

Two variables and a scheduling gap

Let X be the start slot for preparation and Y the start slot for finishing. Both initially have domain {1, 2, 3}. Preparation occupies one slot, so require X + 1 ≤ Y.

The allowed pairs are (1, 2), (1, 3) and (2, 3). X = 3 has no supporting Y and can be removed. Y = 1 has no supporting X and can also be removed. The remaining domains are X in {1, 2} and Y in {2, 3}.

These reduced domains do not make every remaining pair valid: (2, 2) still violates the rule. Choosing X = 2 forces Y = 3.

Now consider a separate example with three variables A, B and C, each in {red, blue}, constrained to differ pairwise. Every value has support in every neighboring variable: red can pair with blue and blue with red. Yet three pairwise-different variables cannot fit into two values. The network is arc-consistent but has no complete solution, illustrating the limit of local support checks.

Illustrative case study

Fictional case: Alder Kits builds a configurator around pairwise compatibility tables. Every selected component passes its adjacent checks, so the first report calls the configuration valid.

A later review finds an omitted total-power requirement involving several components together. The pairwise tables were correct but incomplete as a model of the product. The team adds the global requirement and distinguishes table compatibility from a fully checked configuration.

The lesson is that accurate binary constraints do not automatically express every important business rule. Model coverage and solver correctness are separate responsibilities.

Common misconceptions and mistakes

Binary means a variable has two possible values. It describes the constraint's scope of two variables.
Pairwise compatibility guarantees a global solution. Interacting constraints can make the whole network impossible.
Arc consistency assigns final values. It removes unsupported possibilities but may leave many choices.
Every global rule should be split into pairs. Alternative representations can differ substantially in propagation and size.
A missing constraint is harmless if all existing checks pass. The solver can only enforce the rules actually represented.

Business use

Binary constraints are useful when operational rules naturally concern pairs of choices. They make compatibility relationships inspectable and can support explanations such as identifying the two assignments that conflict.

For implementation reviews, check domain definitions, units and whether equality at a boundary is permitted. Distinguish cannot share a room from prefer not to share a room. Keep small valid and invalid examples for every rule, then test interactions across rules.

Check your understanding

Two variables each have ten possible values and must be different. Is their inequality a binary constraint?

Answer: Yes. It involves two variables. The size of their domains does not change its arity.

Related terms

Learn next

List the allowed pairs for two small scheduling variables. Remove values without support and compare the result with the remaining valid pairs. Then add a third variable and test whether local compatibility is enough to complete the whole assignment.

Sources

AIMA chapter on constraint satisfaction, including constraint arity, propagation and alternative representations: https://aima.cs.berkeley.edu/2nd-ed/newchap05.pdf

AIMA glossary, binary constraint: https://github.com/aimacode/aima-glossary/blob/master/glossary.md?plain=1

Scheduling, colour and kit examples are original illustrations.

Previous: Binary condition Next: Binary cross-entropy