Generalized arc consistency

From Glossary

Jump to: navigation, search

An extension of arc consistency to constraints with more than two variables in their scope.

A variable LaTeX: x is generalized arc consistent (GAC) with a constraint if every value of the variable can be extended to all the other variables of the constraint in such a way the constraint is satisfied.

Generalized arc consistency is one of the most commonly enforced forms of consistency in constraint programming.

GAC has also been called: hyper-arc consistency and domain consistency.


The scope of a constraint is the set of directly constrained variables. For example, in the constraint LaTeX: x \neq y, the set LaTeX: \{x,y\} is the scope.

Personal tools