arc-consistency
Overview
In the provided source, arc-consistency is described through its role in constraint propagation during search. In the labeling phase, the solver iteratively grounds variables (fixes a value for a variable) and then propagates the effect of that choice on other variable domains by applying the same arc-consistency techniques again.
Role in labeling
The source presents labeling as an iterative cycle of:
- choosing a constrained variable,
- grounding it to a value, and
- propagating the consequences to the remaining domains using arc-consistency techniques.
It also notes that this labeling phase can be improved with heuristics for the order in which variables are selected and the order in which values are tried.
Context in STCS
The same work introduces STCS as a dedicated constraint solver intended to improve efficiency for the target constraint problems. STCS maintains two internal domain representations for each variable:
- an interval representation for arithmetic constraints, and
- a bit representation for bit-based constraints.
Propagation is decomposed into bit propagation and interval propagation, and coherence between the two representations is maintained after each modification. In this source, arc-consistency therefore appears as part of a broader propagation-based solving process implemented in STCS.