Solved at Scale

A Bigger Constraint Puzzle

Four nurses, three days, and three shifts form a thirty-six-boolean feasibility model with three constraint families. The instance is parsed from the real model file the external solver reads; no solving happens yet.

highlighted = computed this step

The puzzle

There are 4 nurses, 3 days, and 3 shifts per day, and one boolean per nurse-day-shift combination: 36 booleans in total. Why: the earlier chapters' chain had 3 variables with 3 candidate values each; this instance is the real model the external solver reads, parsed from its model file at build time, not hand-typed into the lesson.

booleans=36\text{booleans}=36
A bigger constraint puzzleThe real scheduling instance: dimensions and constraint families, parsed from the solver's model file.4 nurses, 3 days, 3 shiftsvaluenurses4days3shifts3booleans36coverage9at most one12load rules4min shifts2max shifts3

Three constraint families

Coverage: each day-shift pair is worked by exactly one nurse, 9 rules. At most one: each nurse works at most one shift per day, 12 rules. Load: each nurse works 2 to 3 shifts in total, 4 rules. Why: these are the same kind of local rules as the precedence chain, but there are 25 of them over a much larger space.

coverage+at most one+load\text{coverage}+\text{at most one}+\text{load}
A bigger constraint puzzleThe real scheduling instance: dimensions and constraint families, parsed from the solver's model file.4 nurses, 3 days, 3 shiftsvaluenurses4days3shifts3booleans36coverage9at most one12load rules4min shifts2max shifts3

No solving yet

This lesson only presents the instance. Why: the question is pure feasibility — find one assignment of nurses to shifts that satisfies every rule — and the solving, with its certificate, comes next.

find one feasible assignment\text{find one feasible assignment}
A bigger constraint puzzleThe real scheduling instance: dimensions and constraint families, parsed from the solver's model file.4 nurses, 3 days, 3 shiftsvaluenurses4days3shifts3booleans36coverage9at most one12load rules4min shifts2max shifts3

Diagram note

The table lists the parsed dimensions and the three constraint families with their counts; those labels are the vocabulary this chapter uses everywhere. Pixel positions are rounded for layout; every number shown is exact.

parsed dimensions, not typed\text{parsed dimensions, not typed}
A bigger constraint puzzleThe real scheduling instance: dimensions and constraint families, parsed from the solver's model file.4 nurses, 3 days, 3 shiftsvaluenurses4days3shifts3booleans36coverage9at most one12load rules4min shifts2max shifts3