Two constraint models of the same support rota differ only in encoding, yet one solves in seconds and the other thrashes for hours - what makes the difference?

## Solve time is a property of the model Two models with identical solution sets can differ by orders of magnitude in cost, because the solver does not search the problem - it searches the space the model gave it, using the reasoning the constraint forms permit. This is why experienced modellers treat re-modelling as the first performance lever, ahead of tuning the engine. ## Propagation strength: group versus pairwise A rule can almost always be written more than one way. - As **one group constraint** over many variables: the solver can reason about the group as a whole. If five days have shrunk to the same four candidates, no other day in the group can take any of those four, and it can say so immediately. - As a **pile of pairwise statements**: logically identical, but each one can only remove a value when one of its two variables is actually fixed. The counting argument above is invisible to it. Same solutions, weaker inference, exponentially more nodes. ## Symmetry multiplies identical rosters If four people are genuinely interchangeable for a stretch of the quarter, any roster over them has many equivalent permutations. The consequences are both ways round: - Finding a solution is not much affected - any copy will do. - **Proving** something - infeasibility, or optimality - is badly affected, because the search must refute every copy separately, and refuting one teaches it nothing about the others. The fix is a symmetry-breaking constraint: impose an arbitrary order among the interchangeable elements so exactly one representative of each equivalence class survives. It rules out solutions, which feels wrong until you see that each one it rules out is a relabelling of one it keeps. ## Thrashing, and where it comes from Thrashing is the search failing repeatedly for the same reason in unrelated parts of the tree. The mechanism: 1. Some early guess - a person fixed to a Monday in week 1 - is the real cause of a conflict that only shows up in week 9. 2. The search hits the conflict, and chronological backtracking undoes the **most recent** guess, which is in week 9 and irrelevant. 3. It tries the next week-9 value, hits the same conflict, and repeats across the whole subtree before it ever revisits week 1. The standard answers: | Lever | What it changes | |---|---| | Fail-first variable order | Branch on the most constrained variable, so conflicts surface near the root | | Value order | Try the value most likely to succeed first, shortening the path to a solution | | Conflict-directed backjumping | Undo the guess that actually caused the failure, not the latest one | | Learning the conflict | Record the combination that failed so the same dead end is refuted once | | Restarts | Abandon a bad early branching decision instead of living with it | Fail-first is the counter-intuitive one: branching on the variable with the fewest remaining values makes failures happen sooner and nearer the root, where a refutation removes the most. ## What a re-model actually changes - The **number of variables** and therefore the tree's depth. - The **form of each rule**, and therefore how much each one can infer before anything is fixed. - Whether the objective can bound a **partial** assignment or only a complete one. - How many **equivalent copies** of each solution exist. - What the branching heuristic has to work with - domains that shrink informatively, or flat ones that tell it nothing. ## Where this shows up outside scheduling Solvers hide inside ordinary tooling, and the same encoding effects apply. - **Dependency version resolution**: choosing one version per package such that every declared range is satisfied is exactly a constraint model - variables are packages, domains are published versions, constraints are the ranges. Resolvers that report "no version set satisfies the requirements" are reporting infeasibility, and the good ones report a conflict set with it. - **Constraint-based type inference**: a checker walks the program, collects constraints between unknown types, and solves them, which is why a type error can be reported far from the line that caused it - the conflict is a property of the collected set, not of one expression. ## What interviewers listen for That you locate the fix in the model rather than the engine, that you can name at least one of propagation strength, symmetry and search order with its mechanism, and that you say "can change by orders of magnitude" rather than promising it - re-modelling is a lever, not a guarantee, and some models are slow because the problem is genuinely hard.