skip to content

Your constraint model of the support rota reports infeasible and returns nothing - how do you find which constraints conflict?

level: seniorimportance: should knowfreq 36%

answer

  1. infeasible is a finding, not a fault
  2. data defect or genuine policy clash
  3. capacity arithmetic before any search
  4. delete, re-solve, keep what matters
  5. minimal set, not the smallest one

basics

~20 s

Shrink the model instead of reading it. Drop constraints one at a time and re-solve, keeping only those whose removal restores feasibility. The minimal conflicting set that survives names the handful of rules to renegotiate.

solid answer

~50 s

Infeasible is a finding about your rules, not a crash, so the job is to localise it. First separate data from policy: an empty domain before search - a day where nobody is qualified and available - is usually a data defect, and a counting argument often settles it faster than any solver (90 days needing cover against four people capped at 20 shifts each cannot work). If the rules really do conflict, isolate a **minimal conflicting set** by deletion: remove one constraint, re-solve, and if the model is still infeasible without it, that constraint was not part of this conflict, so leave it out. What remains is a subset that admits no roster and becomes feasible if any single member leaves. It is minimal, not smallest, and there may be several - but each one is a short, concrete list you can take back to the team.

code

pseudocode · 7 lines
pseudocode
function minimal_conflict(constraints):        // constraints are infeasible together
    core = constraints
    for each c in constraints:
        if solve(core without c) = INFEASIBLE:
            core = core without c              // c was not needed for the conflict
        // else: dropping c restored feasibility, so c stays in core
    return core                                // every member now matters

go deeper

for a junior

Understand that infeasible means the rules as written admit no roster, and that the fix is a conversation about the rules rather than a retry.

for a middle

Describe the deletion loop and its test direction: if the model is still infeasible without a constraint, that constraint was not part of the conflict.

for a senior

Show the diagnostic order you would actually use - domains, capacity arithmetic, then conflict isolation by rule family - and expect several conflicts in sequence.

for a principal

The judgement is which rules may ever be soft, since penalty weights silently encode which promise the organisation breaks first when a quarter cannot be covered.

## Infeasible is an answer The solver has proved something: under these rules, no roster exists. That is information about policy, and treating it as a bug in the solver is the first wrong turn. The second is staring at a model of two hundred constraints hoping the conflict is visible. It usually is not, because the conflict is a *combination* - each rule is reasonable and the intersection is empty. ## First, separate data from policy - **Check the domains before search.** If some day's candidate set is already empty - nobody qualified, everyone on leave - the model was broken by its input, not by its rules. - **Do the arithmetic.** Demand against capacity settles a surprising number of cases: days needing cover, multiplied by people per day, against the per-person caps summed over the roster. If supply is short, no conflict-set search is needed. - **Check units and calendars.** Off-by-one on weeks, a quarter with an extra public holiday, a cap expressed per month applied per quarter. ## Isolating a minimal conflicting set The standard technique is deletion-based and needs nothing but repeated solver calls: 1. Start with the full constraint set, known infeasible. 2. Take one constraint `c` and solve without it. 3. **Still infeasible?** Then `c` was not needed for this conflict - drop it permanently and continue. 4. **Feasible now?** Then `c` is part of the conflict - put it back and continue with the next constraint. 5. When every constraint has been tried once, what remains is a **minimal conflicting set**: together they admit no roster, and removing any single member makes them satisfiable. Each pass costs one solve per constraint, so it is worth grouping constraints by rule family first - all consecutive-day rules, all weekend caps - and shrinking families before individual statements. ## Minimal is not minimum This is the distinction candidates most often get wrong. - **Minimal** means no member can be removed without losing the conflict. - **Minimum** means no smaller conflicting set exists anywhere in the model. Deletion gives you minimal, and which minimal set you get depends on the order you tried the constraints in. A model can contain several independent conflicts, and fixing the one you found will simply reveal the next. So re-solve after every fix rather than assuming one report covered everything. ## The alternative: never return nothing For a rota that ships every quarter, an infeasible answer is operationally useless. The standard remedy is to re-model the brittle rules as **soft** constraints: each carries a penalty, the model minimises total penalty, and the output is always a roster plus a list of which rules it broke and by how much. | | All-hard model | Hard core plus soft rules | |---|---|---| | Output when rules clash | Infeasible, nothing to ship | A roster with a named list of violations | | Who decides what gives | The engineer, offline | The penalty weights, stated in advance | | Diagnosis | Conflict-set search after the fact | Readable from the violated rules | | Risk | Blocking at the worst moment | Weights quietly encoding policy nobody agreed | Keep genuinely inviolable rules hard - legal rest periods, a qualification requirement - and soften the preferences. The weights then become a policy artefact the team should review, because they decide which rule bends first. ## What interviewers listen for - That you read infeasible as a statement about the rules. - That you rule out data defects and capacity arithmetic before hunting conflicts. - That you can describe deletion-based isolation without hand-waving, including the direction of its test. - That you say minimal rather than smallest, and expect more than one conflict. - That you know softening is a modelling decision with a policy consequence, not a way of silencing the solver.

  • You fix the conflict the search reported and the model is still infeasible. What happened?
    A minimal conflicting set explains one conflict, not all of them. Independent conflicts can coexist, and deletion finds whichever the constraint order surfaced first. Re-run after each fix and expect a queue; the loop ends when a solve succeeds, not when the first report is addressed.
  • How would you make the rota model report why a rule was broken rather than failing?
    Re-model the negotiable rules as soft constraints with penalties and minimise total penalty, keeping only the inviolable ones hard. The model then always returns a roster together with the rules it violated and by how much, which is an operational answer rather than a dead end - at the price of the weights themselves being policy.
  • Is a conflicting set useful when the real problem is a data feed?
    It still localises the damage, because the conflict will centre on the constraints reading the bad data - typically an availability rule whose domain is empty for one day. But checking the domains for emptiness before search finds that class faster and without the repeated solves.

saying these in an interview costs you the question

  • Treating an infeasible result as a solver bug to be worked around
  • Calling the deletion result the smallest possible conflicting set
  • Assuming exactly one conflict exists once a set is reported
  • Relaxing constraints at random until something returns
  • Skipping the demand-versus-capacity check before hunting conflicts
  • Softening a legally inviolable rule to make the model return