skip to content

A rota solver returns a legal roster in seconds but takes hours to return the one with fewest weekend shifts - why?

level: seniorimportance: should knowfreq 42%

answer

  1. one witness versus a claim about all
  2. first solution ends satisfaction
  3. the bound becomes a constraint
  4. optimum early, proof late
  5. gap or time budget buys the difference

basics

~20 s

Satisfaction stops at the first roster that satisfies every rule. Optimisation must also prove nothing cheaper exists, which means refuting the whole remaining space under a bound. The proof, not the discovery, is what takes hours.

solid answer

~40 s

The two ask different questions. A satisfaction run ends the moment one assignment survives every constraint. An optimisation run has to establish a stronger claim - **no legal roster has a lower cost** - and the only way to establish it is to refute everything still in the space. The usual mechanism is branch and bound: find a roster, read its cost, add the constraint `cost < that`, and search again; when that tightened model finally comes back infeasible, the last roster found is optimal. In practice you reach the optimum early and spend the rest of the run proving it. That is why real systems ask for less than the truth: an acceptable gap, a time budget with best-so-far returned, or a threshold stated as a hard constraint rather than an objective.

code

pseudocode · 12 lines
pseudocode
best = NONE
bound = INFINITY

repeat:
    model.add(total_weekend_days < bound)
    candidate = find_any_solution(model)

    if candidate = NONE:
        return best              // nothing cheaper exists: best is optimal

    best  = candidate
    bound = total_weekend_days(candidate)

go deeper

for a junior

Hold on to the difference between asking for any legal roster and asking for the best one; the second is a claim about every roster you did not see.

for a middle

Explain branch and bound in your own words - each solution tightens a bound that then prunes - and say why the final, fruitless search is the expensive one.

for a senior

Demonstrate that you operate this: give the solver a warm starting bound, set a time budget, keep the best-so-far, and report the gap alongside the roster you ship.

for a principal

The call you own is what the business actually buys with the last hour of proof, and whether a threshold the team can explain is worth more than an optimum it cannot.

## Two different questions - **Satisfaction**: is there an assignment that satisfies every constraint? One witness answers it. - **Optimisation**: among all such assignments, produce one minimising an objective - here, total weekend days worked. A witness is not enough; the claim covers everything that was not produced. That asymmetry is the whole answer. A single roster proves satisfiability. Nothing short of refuting the remaining space proves optimality. ## Branch and bound, step by step 1. Solve the model as a pure satisfaction problem. Say the roster found costs 14 weekend days. 2. Add the constraint `total_weekend_days < 14` and solve again. A roster at 11 comes back. 3. Tighten to `< 11`. A roster at 9 comes back. 4. Tighten to `< 9`. This time the model is infeasible. 5. The 9 is optimal, and step 4 - the search that found nothing - is the one that cost the hours. The bound is not only a stopping rule; it is a constraint like any other, so it propagates. Once the partial assignment has already committed twelve weekend days, a bound of 9 wipes out that branch immediately. A weakly propagating objective is a common cause of slow optimisation: if the solver cannot estimate the cost of a partial assignment, the bound prunes nothing until the assignment is complete. ## Why the optimum arrives early and the proof arrives late Good rosters are not rare; rosters that beat the best by one weekend day are. Early in the run each new solution improves the bound a lot, and the bound cuts a lot. Late in the run the solver is exploring the thin shell of the space where an improvement could still hide, and every node there has to be refuted individually. | | Satisfaction | Optimisation | |---|---|---| | Stops when | One assignment survives | The space under the bound is refuted | | A solution is | The answer | A better bound, and a new constraint | | Cost shape | Usually finds early, fast | Finds early, then proves for a long time | | Useful partial result | None - you have it or you do not | The best roster so far, always usable | | Anytime behaviour | No | Yes | ## The levers, when hours are not available - **Accept a gap.** Ask for a roster provably within, say, one weekend day of the best. The search stops once no remaining branch could beat the bound by more than that margin, and the last stretch of the proof is exactly what you are skipping. - **Give it a good starting bound.** Feed in last quarter's roster, or a heuristic one, as an initial solution. Every branch worse than it is cut before the search begins. - **Cap the time and take best-so-far.** Optimisation is naturally an anytime computation, which satisfaction is not. Production schedulers rely on this. - **Turn the objective into a threshold.** "Nobody works more than six weekend days" is a constraint, propagates like a constraint, and is often what the team actually wants; "minimise weekend days" is a far more expensive request. The risk to weigh is that a threshold set too tight makes the model infeasible, where an objective would simply return the best available. - **Strengthen how the objective is computed** so the solver can bound a partial assignment early rather than only at the leaves. ## What interviewers listen for The direction of the claim, first: candidates routinely say the solver spends its time "searching for the best roster", when it typically had the best roster early and spent the rest proving no better one exists. After that, they listen for whether you know the objective is also a constraint that propagates, and whether you reach for a gap or a time budget rather than assuming an optimisation model must run to completion to be useful.

  • The run is killed by a timeout. Is the roster it had found worthless?
    No - it is legal, because every constraint including the current bound held when it was produced. What you lose is the guarantee that nothing better exists. An optimisation run is an anytime computation: report the best-so-far plus the bound it was proved against, so the team knows how much room might remain.
  • Is the objective propagated like an ordinary constraint?
    Yes, once the bound is added it is a constraint over the same variables and it narrows domains like any other. That is why an objective the solver can only evaluate on a complete assignment optimises badly: the bound cannot cut a partial branch, so the search runs to the leaves before learning anything.
  • Two objectives - fewest weekend days and fairest spread. How do you handle both?
    Either combine them into one scalar with weights, which forces you to state an exchange rate between them, or optimise in priority order: minimise the first, fix it as a constraint, then minimise the second. The second gives cleaner semantics; the first gives the solver more room to trade.

saying these in an interview costs you the question

  • Saying the hours are spent finding the best roster rather than proving it
  • Treating an optimisation model as satisfaction with a sorted output
  • Not knowing the bound acts as a constraint that prunes
  • Discarding the best-so-far roster when the budget runs out
  • Assuming an accepted gap changes which roster is found, not the proof
  • Turning a preference into a hard threshold without weighing infeasibility