skip to content

In a constraint model of a quarterly support rota, what three parts must you declare before a solver can search?

level: juniorimportance: should knowfreq 45%

answer

  1. three parts, no procedure
  2. decisions, alternatives, forbidden combinations
  3. one variable per decision
  4. domains are finite and shrinkable
  5. encoding choice changes the search space

basics

~20 s

Decision variables, one per choice the roster must contain; a finite domain of allowed values for each; and constraints that rule combinations out. The model states no algorithm - the solver owns the search over that space.

solid answer

~40 s

Three parts, and no procedure. **Decision variables**: one per decision the answer has to contain - say `cover[day]`, who is on call each day of the quarter. **Domains**: the finite set of values each variable may take, here the people qualified and available that day. **Constraints**: relations that forbid combinations - nobody covers two days running, each person takes at most six weekend days, a trainee is never alone on a release day. You write nothing about how to build the roster; a solver reads the model and searches. The real design work is choosing the variables, because the same rota can be modelled as one variable per day with people as values, or one yes/no variable per person-day pair, and those two search very differently.

code

yaml · 13 lines
yaml
variables:
  cover:
    index: day_of_quarter
    domain: [ana, ben, cleo, dana]   # who may take that day
  weekend_load:
    index: person
    domain: 0..6                     # counted, not chosen

constraints:
  - cover[day] in available[day]
  - cover[day] != cover[day + 1]
  - weekend_load[p] = count(weekend days where cover = p)
  - weekend_load[p] <= 6

go deeper

for a junior

Be able to take a rota described in prose and point at the decisions, the candidate values for each, and the sentences that forbid combinations. Say out loud that the model contains no steps.

for a middle

Explain why one variable per day and one yes/no per person-day are both correct yet search differently, and where counting rules such as weekend totals live in each.

for a senior

Show that you treat the encoding as a performance decision, prune impossible values before solving, and design for the 'unknown within budget' outcome by keeping the best roster found so far.

for a principal

The judgement is whether a scheduling problem belongs in a declarative model at all: a model is cheap to change when policy changes, and expensive when the team cannot reason about why it returned what it returned.

## The model, not the method A constraint model describes the **answer** as data: what has to be decided, what each decision may be, and which combinations are forbidden. Nothing in it says how to find the roster. A separate engine - the solver - reads the model and searches. You own the model; the solver owns the search. That division is the point. Rota rules change every quarter, and in a constraint model a new rule is one more statement. In a hand-written scheduling loop the same rule is a re-thread of the control flow, because the loop encodes both the rules and the order in which they are satisfied. ## The three parts 1. **Decision variables.** One per decision the answer must contain. For a quarterly rota the obvious set is one variable per day: `cover[day]`. 2. **Domains.** A finite set of candidate values per variable. For `cover[day]`, the people qualified and rostered as available that day. A domain is an explicit list, and the solver is allowed to shrink it as it reasons. 3. **Constraints.** Relations over one or more variables that rule combinations out: no person on two consecutive days, at most six weekend days per person, every day covered exactly once. ## Variables are where the design happens - A variable exists for something the **answer** needs decided. Who covers 14 March is a decision; the fact that 14 March is a Saturday is data. - Quantities you only want to bound can still be variables, tied to the others by a constraint: `weekend_load[person]` counts weekend days assigned to that person, and a second constraint caps it. The solver narrows it as the assignment fills in. - Domains must be **finite and enumerable** for this style of solver. "Any start time" is not a domain; "one of these 24 hourly slots" is. - Every value you leave in a domain is a branch the search may have to explore, so pruning impossible values up front - a person on leave, a person without the qualification - is free work. ## Two encodings of the same rota | Question | One variable per day | One yes/no variable per person-day | |---|---|---| | How many variables | One per day in the quarter | People times days | | "Every day covered exactly once" | Implicit: each variable takes one value | An explicit sum-to-one constraint per day | | "At most six weekend days each" | A counting constraint over the day variables | A sum over that person's weekend flags | | Typical propagation | Strong on per-day rules | Strong on per-person totals | Both are correct models of the same rota. They present the solver with different search spaces, which is why encoding is a performance decision and not a matter of taste. ## Hard, soft and global constraints - A **hard** constraint must hold in any answer; violating it means there is no answer. - A **soft** constraint is a preference with a penalty, and it only means something alongside an objective to minimise - otherwise the solver has no reason to prefer one legal roster over another. - A **global** constraint is one statement over many variables - "these seven days all take different people" - rather than the pile of pairwise inequalities that says the same thing. It is the same solution set, but a solver reasons about the group as a whole and rules out more, earlier. ## What the solver hands back - An **assignment**: a value for every variable that satisfies every constraint. - **Infeasible**: a proof that no such assignment exists. This is a finding about your rules, not a bug. - **Unknown**: it ran out of its time budget without either. Candidates forget this third outcome, and it is the one production systems must handle - usually by returning the best roster found so far. ## What interviewers listen for They want to hear you separate the model from the search, and then hear you treat the variable choice as a decision with consequences rather than a transcription of the problem statement. A candidate who says "variables, domains, constraints" and stops has recited a definition. A candidate who says "I would try one variable per day first, because the cover-exactly-once rule then costs nothing to state, and switch if the per-person totals propagate badly" is doing the job.

  • Where in the model would you put "prefer not to roster anyone on the day after a release"?
    It is a preference, not a rule, so it becomes a soft constraint: a penalty term that is added whenever the pattern occurs, plus an objective that minimises total penalty. As a hard constraint it could make an otherwise workable quarter infeasible, and with no objective in the model a soft constraint has no effect at all.
  • Does a solver need the domains to be finite?
    The finite-domain style described here does: it reasons by removing candidate values, which needs an enumerable set. Continuous quantities need a different family of solver, or a discretisation - hourly slots instead of arbitrary start times. Saying which you are modelling matters, because it decides the whole toolchain.

It is the difference between handing someone the finished shopping list and handing them the dietary rules the week has to satisfy; the rules survive a change of menu, the list does not.

saying these in an interview costs you the question

  • Describing the loop that builds the roster instead of the model
  • Treating a domain as a data type rather than an explicit candidate set
  • Making every fact a decision variable, including fixed calendar data
  • Adding soft constraints with no objective to minimise
  • Assuming the solver returns a solution or an error, never 'unknown'