Variables & Domains

Variables and Domains

Constraint propagation starts with variables, finite domains, and constraints between variables. A domain is the set of values still possible for a variable, and a constraint is a reason to erase values that cannot work. In this toy schedule, tasks A, B, and C begin with the same possible slots before precedence constraints start shrinking the grid.

highlighted = computed this step

Variables and slots

There are 3 task variables A, B, and C. A variable is not assigned immediately; it carries a domain of values that are still possible. Why: CP starts by representing uncertainty explicitly, then lets constraints erase values that cannot survive.

vars=3\text{vars}=3
initial domains123A123B123C123

Full domains

Each task starts with domain {1,2,3}. At this point every shown value is a candidate value for every task. Why: propagation has not yet used any precedence information, so the model has no reason to prefer or erase a slot.

DA=DB=DC={1,2,3}D_A=D_B=D_C=\{1,2,3\}
initial domains123A123B123C123

Precedence constraints

The precedence chain is A<B<C. Each inequality is a local rule, but repeated together they can carry information through the whole chain. Why: propagation tries to shrink the search space before any branching choice is made.

A<B<CA<B<C
initial domains123A123B123C123

Diagram note

The unstyled cells are candidates still in the recomputed domains. The diagram is the starting state for exact deterministic domain reduction, not a guess at the final schedule. This is the CP-SAT entry idea in miniature: keep the possible set explicit, then let constraints make it smaller before search. Pixel positions are rounded for layout; every number shown is exact.

propagation starts from exact finite domains\text{propagation starts from exact finite domains}
initial domains123A123B123C123