Constraint Solvers and the Problems They Own

Scheduling, rostering, routing, allocation and packing are not language problems that happen to be hard. They are combinatorial optimisation problems with a mature, free, well-understood body of technology behind them, and the useful distinction is not accuracy — it is that a solver can prove things about its answer and a sampler cannot.

The shape of a solver problem

A problem belongs to a solver when it has all three of these:

• Decision variables with finite domains. Which nurse works which shift; which van carries which parcel; which order goes on which machine.
• Hard constraints that must hold in any acceptable answer. Rest periods between shifts, vehicle capacity, a qualified operator on every machine. A solution that violates one is not a worse solution; it is not a solution.
• An objective to optimise, subject to those constraints. Minimise overtime, minimise distance, balance weekend shifts fairly.

The presence of hard constraints is the tell. If some outputs are simply inadmissible rather than merely poor, you need a method that searches only the admissible region — which is what a constraint solver does by construction.

The search space, computed

Take a small, entirely realistic instance: one ward, twelve nurses, seven days, three shifts a day, three nurses required on each shift. That is 21 shifts to fill.

ways to staff ONE shift with 3 of 12 nurses:
  C(12,3) = 12! / (3! * 9!) = (12 * 11 * 10) / 6 = 220

assignments across all 21 shifts, ignoring every constraint:
  220 ^ 21

  log10(220)      = 2.3424
  2.3424 * 21     = 49.19
  10 ^ 49.19      = 1.55 x 10^49

so roughly 1.5 x 10^49 candidate rosters before any rule is applied.

For scale: enumerating one candidate per nanosecond on a billion cores in parallel would still take on the order of 10²³ years. The constraints cut that space enormously — that is exactly what they are for — but no amount of enumeration reaches it, and the answer is not found by looking at candidates one at a time.

Two things follow. A person building the roster by hand is not searching this space; they are applying heuristics and settling for the first thing that works, which is why hand-built rosters are feasible and rarely good. And a language model asked to produce a roster is sampling one plausible-looking assignment, with no mechanism that checks the rest hours or the skill mix, let alone the cost.

The model, in CP-SAT

Google OR-Tools’ CP-SAT solver is free, open source and the standard starting point. The model is the problem, stated:

from ortools.sat.python import cp_model

nurses  = list(range(12))
days    = list(range(7))
shifts  = [(d, s) for d in days for s in range(3)]   # 0=early 1=late 2=night
senior  = {0, 1, 2, 3}
requested_off = {(4, (2, 0)), (7, (5, 1))}           # nurse, shift

model = cp_model.CpModel()
x = {(n, sh): model.NewBoolVar(f"x_{n}_{sh}") for n in nurses for sh in shifts}

# 1. every shift needs exactly 3 nurses
for sh in shifts:
    model.Add(sum(x[n, sh] for n in nurses) == 3)

# 2. at least one senior nurse on every shift
for sh in shifts:
    model.Add(sum(x[n, sh] for n in senior) >= 1)

# 3. at most one shift per nurse per day
for n in nurses:
    for d in days:
        model.Add(sum(x[n, (d, s)] for s in range(3)) <= 1)

# 4. no early shift the day after a night shift (rest period)
for n in nurses:
    for d in days[:-1]:
        model.Add(x[n, (d, 2)] + x[n, (d + 1, 0)] <= 1)

# 5. at most 3 consecutive night shifts
for n in nurses:
    for d in range(len(days) - 3):
        model.Add(sum(x[n, (d + k, 2)] for k in range(4)) <= 3)

# 6. between 3 and 5 shifts per nurse per week
for n in nurses:
    total = sum(x[n, sh] for sh in shifts)
    model.Add(total >= 3)
    model.Add(total <= 5)

# objective: honour requested days off, then balance night shifts
violations = sum(x[n, sh] for (n, sh) in requested_off)

night_counts = []
for n in nurses:
    c = model.NewIntVar(0, 7, f"nights_{n}")
    model.Add(c == sum(x[n, (d, 2)] for d in days))
    night_counts.append(c)

spread = model.NewIntVar(0, 7, "night_spread")
model.AddMaxEquality(spread, night_counts)

model.Minimize(100 * violations + spread)

solver = cp_model.CpSolver()
solver.parameters.max_time_in_seconds = 30.0
status = solver.Solve(model)

if status == cp_model.OPTIMAL:
    print("proved optimal, objective =", solver.ObjectiveValue())
elif status == cp_model.FEASIBLE:
    print("feasible within the time limit, objective =", solver.ObjectiveValue(),
          "best possible bound =", solver.BestObjectiveBound())
elif status == cp_model.INFEASIBLE:
    print("no roster satisfies these constraints")
else:
    print("no solution found within the time limit")

That is fifty lines and it is the whole system. Every rule is one or two lines, adding a rule does not require rewriting anything, and the constraints are stated in the same language a ward manager would use. Notice constraint 5 in particular: “at most three consecutive night shifts” is expressed as a sum over a sliding window of four, which is the standard encoding for consecutive-run limits and is worth recognising because it recurs everywhere.

What each approach can certify

The middle row is the one that is usually decisive commercially. A roster that satisfies every rule but uses 14% more overtime than necessary costs real money every week, and nothing about the roster itself reveals that. The bound does.

The point is not that a model produces bad rosters. It is that neither you nor it can tell whether a given roster is good, feasible, or the only one, and those are precisely the questions the problem is about.

When there is no answer

Over-constrained problems are the normal case in production. Somebody adds a rule, and suddenly no roster exists. INFEASIBLE is correct and unhelpful on its own, so build the diagnosis in from the start:

1. Separate hard from soft constraints deliberately. Legal rest periods are hard. Requested days off are preferences and belong in the objective with a penalty weight, as violations is above. Most infeasibility is caused by a preference that was encoded as a rule.
2. Ask the solver which constraints conflict. CP-SAT supports assumption literals and can report a subset of assumptions sufficient to explain infeasibility, which turns “no solution” into “these three rules cannot all hold”.
3. Relax systematically. Add a slack variable to each soft constraint with a large penalty, so the solver always returns something and reports exactly which rules it had to break and by how much. A roster with two named violations is far more useful than no roster.
4. Report the binding constraint. “You need at least one more senior nurse to cover next week” is the output the manager actually wants, and it comes out of the relaxation, not out of the solution.

Where the model belongs

Not deciding — translating and explaining, on both sides of the solver:

• Before. Turning “Ines cannot do nights this month because of her course, and we need two seniors on at weekends” into constraint expressions, presented to a human for confirmation before they enter the model. This is the same translate-then-validate pattern as text-to-Cypher, and it needs the same validation step for the same reason.
• After. Explaining the result in prose: why somebody has three nights, which rule forced it, what would have to change. The solver has the facts; the model has the sentence.
• Around. Handling the parts of the workflow that are genuinely language — the request that arrives by email, the summary that goes out, the question about last month’s roster.

This is the same division of labour as a rules engine next to a model, with one extra property: a rules engine applies a decision somebody already made, while a solver makes a decision nobody could have made by hand. That is why the two are worth separating even though they sit on the same side of the line.