Constraint Solving with Dirty Inputs

Our CP-SAT solver schedules activities during employees' shifts. On a typical day, that means deciding when 30, 50, or 100 people should take a break, work the chat channel, answer phone calls, or spend time on admin.

Planners can configure a long list of constraints. The original idea was simple: run the solver, get back a schedule, and know it stays within the mandated boundaries.

What we did not expect was how often schedulers would break those same boundaries themselves, then still expect the system to produce a useful result.

A concurrency limit might already be exceeded before the solver ran. Someone might already be over their allowed minutes. A block might already violate placement or length rules. Some work was already assigned and could not realistically be moved.

Our first instinct was to treat those cases as infeasible. That was clean, but not very helpful. The schedule still had to be updated. People still needed instructions. "No solution found" was often technically correct and operationally useless.

That pushed us from infeasible city to practical correctness.

The solver was no longer trying to build a perfect schedule from scratch. It was trying to improve a schedule that already contained fixed commitments and existing violations. In practice, that meant preserving baseline assignments and making sure new assignments did not make existing problems worse.

When Infeasible Stopped Being Useful

Constraint solvers look neat on whiteboards. You define workers, activities, and rules. The solver finds a valid schedule or proves none exists. That works well when the input is clean.

Production systems are not clean. A scheduler inherits partially assigned shifts, manual overrides, upstream data issues, and planners who are willing to violate their own rules when the day gets messy enough.

Once that happens, infeasibility stops being a satisfying answer. The schedule still needs to move forward.

From Infeasible City to Practical Correctness

The biggest change was in what we asked the solver to do. At first, the model treated constraints in the obvious way. If the schedule violated a hard rule, the solver could fail. That approach was consistent, but it assumed the input was already valid.

In practice, that assumption broke quickly.

So we moved to a narrower goal. The solver should preserve the current state where it had to, improve the schedule where it could, and avoid making existing violations worse.

Constraints still mattered. We just stopped applying them in the same way to inherited baseline state and new decisions. The baseline might already be wrong. New assignments still had to behave correctly.

Treating Existing Work as Baseline

A pre-assigned activity is not just another variable in the model.

If someone is already scheduled from 09:00 to 10:00, that assignment may already exist in other systems. It may already have been communicated. It may already have operational consequences.

So we treated pre-assigned work as baseline state. The solver preserved it even when it conflicted with the current configuration. That is what turned the problem from pure optimization into schedule repair.

A Rule That Worked Better Than Strict Enforcement

The most useful rule we found was simple: if the baseline already violates a constraint, preserve it, and prevent new assignments from making it worse.

Take concurrency. Suppose an activity is supposed to have at most one worker at a time, but the incoming schedule already has two people assigned during the same interval.

A strict model can reject the whole solve. A more practical model accepts the existing overage and stops the solver from adding a third worker, extending the over-limit period, or creating the same issue elsewhere.

We ended up using the same idea in several places. Existing max breaches could remain as baseline state. New assignments were blocked from worsening them. Existing block-length or gap violations could remain. New placements still had to respect the configured rules.

This was the move from infeasible city to practical correctness in its simplest form.

Why We Tried to Avoid Infeasibility

Some combinations of constraints really are impossible. Infeasibility did not disappear. But we became much more careful about reaching it. A planner can often work with a shortfall or a compromise. They cannot do much with a solver that simply refuses to return a schedule.

That led us to separate constraints that truly had to be met from constraints that should push the schedule in the right direction without collapsing the solve.

In practice, that often meant distinguishing “Must Meet” from “Best Effort”.

A hard minimum can make the schedule infeasible. A best-effort minimum applies pressure but lets the solve continue when capacity or baseline state makes the target unattainable.

Explicitly Paying for Imperfection

Another decision that helped was making unscheduled time explicit. Instead of forcing every slot into a productive activity, we allowed an unscheduled fallback with a high penalty.

That gave the solver somewhere to go when the alternative was contradiction. It also made the tradeoff visible. The model was not pretending everything fit neatly. It was paying a clear cost for leaving part of the schedule unresolved. That is much easier to reason about than a silent failure or an opaque infeasible.

Dirty Inputs Are Normal

One useful lesson here was that dirty input is not an edge case. It is the default condition of a production system. Schedulers make manual changes. Some of those changes break the rules. Upstream systems emit malformed fragments. Rules evolve over time, but old assignments remain.

You can try to clean all of that before the solver runs, and you should. But the solver also needs to survive the parts that still get through.

That means preserving unknown pre-assigned activities if they already exist in the schedule. It means handling malformed configuration defensively. It means accepting that the current state may already be inconsistent, then deciding how much of that inconsistency can be contained.