How do you balance candidate completeness vs model explosion?

[Soryie]

Hi all,

I'm building a workforce scheduling solver using Python and OR-Tools CP-SAT, and I've hit a modelling problem where I'd really appreciate some advice from people with more CP-SAT experience.

The solver schedules roughly 15–55 employees across a 7-day week, with things such as:

• time-varying staffing demand

• multiple roles / areas

• employee availability

• holidays

• minimum / maximum shift lengths

• fixed/manual shifts

• contract-hour preferences

• role capability

• hard maximum staffing / no unnecessary overstaffing

Demand is evaluated on atomic time slots.

The important hard requirement is:

If a week is mathematically feasible, we want 100% demand coverage without exceeding demand in any slot.

Current modelling approach

Rather than creating arbitrary start/end variables for every employee, we currently pre-generate candidate shifts and CP-SAT selects from those candidates.

This works well when the candidate universe contains the right shift topology.

However, we've recently built a much larger acceptance harness using known-feasible generated weeks. We first construct a valid hidden rota, derive demand/availability from it, throw the rota away, and ask the solver to rediscover a solution.

This exposed an interesting issue.

Some weeks are provably 100% coverable, but the solver only reaches 99.x%.

When we inspect the candidate universe, the missing coverage is often because the required handover shape was never generated.

For example, conceptually:

Employee A: 09:00–13:30 Employee B: 13:30–18:00

may be a valid tiling of a demand=1 interval.

But if candidate endpoints only exist at certain block boundaries or heuristic split points, the 13:30 handover doesn't exist in the candidate universe.

So CP-SAT is correctly finding the best solution in the model — the model simply cannot represent the known feasible rota.

First attempt: enrich candidate geometry

We started adding additional handover points.

Initially:

block edges + heuristic split points

Then:

+ hourly handover grid

Then:

+ half-hour handover grid + prefix/suffix shifts + interior start/end pairs

Coverage improves significantly as candidate geometry becomes richer.

But candidate count starts exploding.

At around 50–55 employees, expanding the candidate universe approximately tripled candidate volume in some fixtures, and a secondary enrichment/recovery stage became extremely slow — one benchmark ran for over 30 minutes without completing.

So we're now stuck between:

Too few candidates → fast model → known feasible solutions may not exist in the candidate universe Too many candidates → candidate universe contains the solution → model becomes very large / slow The question

What is the idiomatic CP-SAT way to model this?

I'm considering a few possibilities:

1. Continue pre-generating shift candidates, but design a much smarter sparse candidate-generation scheme.

2. Generate candidates iteratively:

   • solve

   • inspect uncovered slots

   • add promising candidates

   • solve again

   Essentially a lightweight column-generation-style approach, although CP-SAT obviously isn't a traditional LP column generation solver.

3. Model shift start/end decisions more directly rather than pre-enumerating complete shift candidates.

4. Use interval variables / optional intervals and constrain allowed start/end combinations.

5. Represent coverage at atomic slots and let CP-SAT construct contiguous working runs itself.

6. Use a hybrid approach:

   • small high-quality base candidate set

   • solve

   • targeted enrichment only around uncovered demand

   • bounded re-solve

Constraints that make this slightly harder

We cannot simply allow arbitrary assignments per atomic slot because shifts must remain operationally sensible and contiguous.

We also have:

• minimum shift duration

• maximum shift duration

• role-specific coverage

• employee availability boundaries

• some employees who can work full-root / long shifts

• others who should use normal handover structures

• contract-hour preferences

• fixed obligations

• multiple areas

• no simultaneous overstaffing above configured demand

Coverage is lexicographically more important than soft preferences, but hard constraints must never be violated to obtain coverage.

One other thing we've observed

The larger 50+ employee fixtures can show some run-to-run variability when the candidate universe gets large and solve limits become relevant.

So I'd also be interested in any advice around keeping this type of scheduling model reasonably deterministic/reliable under a fixed runtime budget.

What I'm trying to understand

The main architectural question is:

For workforce scheduling in CP-SAT, would experienced users normally enumerate legal complete shifts beforehand, or model the shift boundaries directly and let CP-SAT determine the topology?

And if candidate enumeration is still the right approach:

How do you avoid needing something close to the Cartesian product of possible start/end points to guarantee that valid handovers remain representable?

I'd particularly appreciate pointers toward patterns such as optional intervals, automata, reservoir/cumulative modelling, alternative formulations, or examples from similar employee scheduling problems.

I'm very happy to provide a stripped-down model / small reproducible fixture if that would help.

Thanks!

[blind.lin...@gmail.com]

I just wanted to reply that your question is very interesting even though right at this moment I personally do not have time to think about it and reply. But it is very interesting/challenging. On the one hand you want the fine-grained time steps to give you the 100% coverage, but on the other, as you said, the search space explodes when you do that. Is there a way to cut out the irrelevant search space in the "half-hour handover" grid?

James

On Tue, Sep 08, 2026 at 07:59:12AM -0700, Soryie wrote:

Hi all,

I'm building a workforce scheduling solver using Python and OR-Tools CP-SAT, and I've hit a modelling problem where I'd really appreciate some advice from people with more CP-SAT experience.

The solver schedules roughly 15–55 employees across a 7-day week, with things such as:

time-varying staffing demand
-

multiple roles / areas
-

employee availability
-

holidays
-

minimum / maximum shift lengths

-

fixed/manual shifts
-

contract-hour preferences
-

role capability
-

2.

Generate candidates iteratively:
-

  solve  
  - 
  
  inspect uncovered slots  
  - 
  
  add promising candidates  
  - 
  
  solve again  
  

Essentially a lightweight column-generation-style approach, although CP-SAT obviously isn't a traditional LP column generation solver.

3.

Model shift start/end decisions more directly rather than pre-enumerating complete shift candidates.

4.

Use interval variables / optional intervals and constrain allowed start/end combinations.

5.

Represent coverage at atomic slots and let CP-SAT construct contiguous working runs itself.

6.

Use a hybrid approach:
-

  small high-quality base candidate set  
  - 
  
  solve  
  - 
  
  targeted enrichment only around uncovered demand  
  - 
  
  bounded re-solve  
  

Constraints that make this slightly harder

We cannot simply allow arbitrary assignments per atomic slot because shifts must remain operationally sensible and contiguous.

We also have:

minimum shift duration
-

maximum shift duration
-

role-specific coverage
-

employee availability boundaries
-

some employees who can work full-root / long shifts

-

others who should use normal handover structures

-

contract-hour preferences
-

fixed obligations
-

multiple areas
-

no simultaneous overstaffing above configured demand

Coverage is lexicographically more important than soft preferences, but hard constraints must never be violated to obtain coverage.
One other thing we've observed

The larger 50+ employee fixtures can show some run-to-run variability when the candidate universe gets large and solve limits become relevant.

So I'd also be interested in any advice around keeping this type of scheduling model reasonably deterministic/reliable under a fixed runtime budget.
What I'm trying to understand

The main architectural question is:

For workforce scheduling in CP-SAT, would experienced users normally enumerate legal complete shifts beforehand, or model the shift boundaries directly and let CP-SAT determine the topology?

And if candidate enumeration is still the right approach:

How do you avoid needing something close to the Cartesian product of possible start/end points to guarantee that valid handovers remain representable?

I'd particularly appreciate pointers toward patterns such as optional intervals, automata, reservoir/cumulative modelling, alternative formulations, or examples from similar employee scheduling problems.

I'm very happy to provide a stripped-down model / small reproducible fixture if that would help.

Thanks!

-- You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/or-tools-discuss/c54434ff-c054-48bf-b19b-5c11cc59dcd0n%40googlegroups.com.

--

James E. Marca  
Activimetrics LLC  

[Soryie]

Hi James,

Thanks again — your question ended up being exactly the right one.

We’ve now pushed the investigation much further, and the answer appears to be yes: we can cut out a lot of the irrelevant half-hour search space, but only if we preserve the endpoints that are structurally meaningful to feasibility.

We built a fairly aggressive acceptance harness around the solver, including 250 generated known-feasible weeks where a valid hidden rota is created first and then discarded. That gives us an oracle: if the solver returns below 100% coverage, we know the input itself was feasible.

Initially, several large 50–55 employee weeks were failing because the exact handover shapes from the planted feasible rota were being sampled out of the candidate universe.

The key change was to stop treating all half-hour endpoints equally.

The candidate generator now preserves shapes whose endpoints coincide with structural events such as:

• hourly anchors
• demand transitions for the staffing unit
• fixed-shift boundaries
• availability boundaries

Those shapes are never sampled away.

The remaining clock-only prefixes/suffixes are budgeted separately, and the interior half-hour start/end pairs are the family that can be thinned most aggressively.

That fixed the “missing topology” problem without exploding the candidate universe.

We then found a second bottleneck downstream: the Area/role labelling model was multiplying those candidates into a huge number of variables. One large case had roughly 107k assignment variables and 50k transition variables.

We reduced those cut points to only structural events that can actually change who is able to satisfy the Area composition requirement. In one representative large fixture, that brought the labelling model down to under 8k assignment variables.

We also made the choice between the richer and reduced candidate universe based on a measured labelling-weight estimate, not raw candidate count, because candidate count alone turned out to be a poor predictor of model difficulty.

The final result is:

• deterministic/impossible/readiness suite: 102/102
• generated known-feasible suite: 250/250 at 100.00% coverage
• customer-readiness suite repeated five times: 28/28 every time
• zero hard-constraint violations
• zero overstaffing
• zero runtime failures under our 150s bound

Some of the previously failing large cases changed quite dramatically. For example:

• one fixture went from ~99.45% with 13,026 candidates to 100% with 8,639 candidates
• another went from 92.85% to 100% with a somewhat richer but structurally better candidate set

So in the end, the important factor was not “more candidates”, but which candidates survived.

The formulation is still candidate-based rather than fully switching to direct start/end decision variables, but the candidate universe is now much more structural and the local enrichment stage only widens around remaining short lanes.

I’d still be very interested in whether you think this is a sensible long-term CP-SAT pattern, or whether you’d ultimately prefer moving the shift boundaries into the model more directly.

Thanks again — your comment about cutting irrelevant search space in the half-hour grid turned out to be exactly where the breakthrough came from.

Dylan

[Laurent Perron]

This is really impressive work. Worth of a blog post or something visible. 

Thanks James for stepping in.

--Laurent

To view this discussion visit https://groups.google.com/d/msgid/or-tools-discuss/902366a3-399d-4af0-b987-4817ded9c4b2n%40googlegroups.com.

[blind.line]

I'm glad my question was helpful. Thanks for the follow-up report too--there is a lot of stuff here to think about and learn from. 

James

On Sep 10, 2026, at 01:42, Laurent Perron <laurent...@gmail.com> wrote:



To view this discussion visit https://groups.google.com/d/msgid/or-tools-discuss/CAPyyUTsH2E4fzLmc-5q-x65KreDcS6Ub2W300QUkm1g0Kg4S1Q%40mail.gmail.com.