Tuning CP-SAT for Large-Scale Rostering

The scaling challenge

A CP-SAT model for employee scheduling grows in three dimensions simultaneously: more employees, more shift types, and more days. A model for 100 employees with 40 shifts over 30 days contains roughly 80,000 Boolean variables. Double the employees and you more than double the model size, because cross-employee constraints (equity, coverage) grow quadratically.

At 100 employees, CP-SAT typically solves the problem in under 3 minutes. At 200 employees, naive configurations can take over 30 minutes or time out entirely. The difference between a well-tuned and a poorly-tuned solver configuration is often the difference between a usable system and one that frustrates planners.

This article covers the practical levers available to you: time limits, parallelism, model reduction, symmetry breaking, and propagation. Each technique is independent and their effects compound.

Time limits and anytime behaviour

CP-SAT is an anytime solver. It does not need to finish to be useful. At any point during the search, it holds the best feasible solution found so far. If you stop it early, you get that solution. If you give it more time, it may find a better one.

The time limit is set via:

solver.parameters.max_time_in_seconds = 300  # 5 minutes

When the time limit is reached, the solver stops and returns the best solution found along with the objective value and the optimality gap (the distance between the best solution and the proven lower bound).

This anytime property changes how you think about tuning. The question is not "will it solve?" but "how good will the solution be within my time budget?" For most rostering problems, the solver finds a good solution in the first 10-20% of the allotted time, then spends the remaining time making incremental improvements.

Choosing a time limit

The right time limit depends on the problem size and the planner's workflow. A monthly schedule is generated once per month, so even 30 minutes is acceptable. An interactive re-solve after a manual edit should complete in under 2 minutes.

# Practical guidelines:
# 100-150 employees:  max_time = 300   (5 min)
# 150-200 employees:  max_time = 900   (15 min)
# 200-300+ employees: max_time = 1800  (30 min)

Multi-threaded search

CP-SAT's parallelism is not data parallelism. It does not split the problem into independent subproblems. Instead, it runs multiple search strategies simultaneously on the full model. Each worker thread explores the search tree using a different heuristic: one may prioritise coverage variables, another may focus on equity, a third may use random restarts.

All workers share a global solution pool. When one worker finds a better solution, the others are immediately notified and can use it to prune their own search. This architecture means that adding workers does not simply divide the time by N. The speedup comes from strategy diversity: different heuristics find different parts of the solution space, and the best discoveries are shared.

Setting num_workers

solver.parameters.num_workers = 8  # Match your CPU core count

The default value is typically the number of available CPU cores, but it is worth setting explicitly. On a machine with 8 physical cores, num_workers = 8 is the sweet spot. Going beyond the physical core count (e.g. 16 workers on 8 cores) gives marginal returns because workers compete for CPU time rather than running truly in parallel.

Why more workers help

With 1 worker, the solver uses a single search strategy. If that strategy gets stuck in an unproductive region of the search space, there is no recovery except random restarts. With 8 workers running 8 different strategies, the probability of all workers being stuck simultaneously is much lower. In practice, the solver with 8 workers finds the same quality solution in 3-5x less time than with 1 worker.

Monitoring search progress

solver.parameters.log_search_progress = True

This prints a line every time a worker finds a new best solution, showing which strategy found it, the objective value, and the current optimality gap. It is invaluable for understanding which workers are contributing and whether the solver is still making progress.

Variable space reduction

The single most impactful modelling technique is to not create variables for impossible assignments. Every assign[e, d, s] variable that the solver can never set to 1 is wasted memory and wasted search effort.

Qualification filtering

If employee e does not hold the qualification for shift s, do not create assign[e, d, s] at all. With 300 employees and 50 shifts, each employee is typically qualified for 15-25 shifts. This alone removes 50-70% of potential variables.

# Instead of:
for e in employees:
    for d in days:
        for s in shifts:
            assign[e, d, s] = model.NewBoolVar(...)

# Do:
for e in employees:
    for d in days:
        for s in qualified_shifts[e]:
            assign[e, d, s] = model.NewBoolVar(...)

Absence filtering

If employee e has a pre-assigned absence (holiday, vacation, fixed day off) on day d, do not create any assign[e, d, s] variables for that day. Fix is_off[e, d] = 1 directly.

# For each absence:
if employee_absent(e, d):
    model.Add(is_off[e, d] == 1)
    # Skip creating assign[e, d, *] entirely

With an average of 4-6 absence days per employee per month, this removes another 15-20% of the remaining variables.

Combined impact

Qualification filtering plus absence filtering typically reduces the model by 30-50% compared to the naive approach. For a 300-employee problem, this means going from ~450,000 Boolean variables to ~225,000-315,000. The constraint count drops proportionally, and the solver's propagation becomes significantly faster.

Symmetry breaking

Symmetry is one of the most subtle performance killers in scheduling models. Two employees with identical qualifications, identical contract types, identical constraints, and no pre-assigned absences are interchangeable. The solver does not know this. It will explore both "Alice gets shift A on Monday, Bob gets shift B" and "Bob gets shift A on Monday, Alice gets shift B" as different solutions, even though they are functionally equivalent.

For a group of K interchangeable employees, there are K! equivalent assignments. With 5 interchangeable employees, that is 120 equivalent permutations the solver wastes time exploring.

Ordering constraints

The simplest symmetry-breaking technique is to impose an arbitrary ordering. If employees e1 and e2 are interchangeable, require that e1's first working day is no later than e2's.

# For interchangeable employees e1, e2 (e1 < e2):
# e1's total shifts >= e2's total shifts
model.Add(total_shifts[e1] >= total_shifts[e2])

This does not change the quality of the solution. It simply eliminates half of the equivalent permutations, directing the solver to explore only the "canonical" ordering.

Identifying interchangeable employees

Two employees are interchangeable if they share the same qualification set, the same contract type, the same group membership, and neither has any pre-assigned absences or individual constraints. In practice, truly interchangeable pairs are uncommon in real scheduling data (3-8 per model), but even a few symmetry-breaking constraints can measurably reduce solve time.

Propagation tips

CP-SAT's core strength is constraint propagation: deducing variable assignments from existing constraints without searching. The more information the propagator can extract, the smaller the search tree becomes.

Pre-compute toxic pairs

The 11-hour rest constraint between consecutive days can be encoded as time arithmetic or as Boolean implications. The implication form is far more efficient.

# Slow: time arithmetic in the model
model.Add(end_time[s1] + 660 <= start_time[s2])
    .OnlyEnforceIf(assign[e, d, s1], assign[e, d+1, s2])

# Fast: pre-computed Boolean implication
# Pre-compute once: toxic_pairs = [(s1, s2) where end(s1) + 660 > start(s2)]
for (s1, s2) in toxic_pairs:
    model.Add(assign[e, d, s1] + assign[e, d+1, s2] <= 1)

The Boolean form triggers stronger propagation. When assign[e, d, s1] = 1, the solver immediately deduces assign[e, d+1, s2] = 0 for all toxic partners. The time arithmetic version requires the linear relaxation to discover this, which is slower.

Use implications instead of big-M

Big-M constraints (using a large constant to linearise conditional logic) are a common pattern from MIP modelling. CP-SAT handles them, but they weaken the linear relaxation and produce poor bounds.

# Avoid big-M:
model.Add(coverage[f, d] >= need[f, d] - M * slack[f, d])

# Prefer direct penalty variables:
model.Add(coverage[f, d] + missing[f, d] >= need[f, d])
model.Add(missing[f, d] >= 0)

Direct penalty variables give CP-SAT tighter bounds, which means better pruning and faster convergence to optimal solutions.

Leverage AddBoolOr and AddBoolAnd

When expressing logical relationships between Boolean variables, use CP-SAT's native Boolean operations rather than linear arithmetic. AddBoolOr and AddBoolAnd trigger specialised propagators that are significantly faster than their linear equivalents.

# Instead of: assign[e, d, s1] + assign[e, d, s2] >= 1
model.AddBoolOr([assign[e, d, s1], assign[e, d, s2]])

Benchmarks

Measured on a standard server (8 cores, 16 GB RAM) with a real-world rostering model (40-50 shift types, 30 days, multiple functional groups, full constraint set). Time shown is time to reach the best solution found within a 30-minute window.

Employees	1 worker	4 workers	8 workers	16 workers
100	8 min	3 min	2 min	1.8 min
150	15 min	6 min	4 min	3.5 min
200	30+ min	12 min	8 min	7 min
300	timeout	25 min	15 min	12 min

Key observations:

• Going from 1 to 4 workers gives the largest speedup (2-3x). This is because 4 diverse strategies are much better than 1.
• Going from 4 to 8 workers adds another 1.5-2x. The marginal strategy diversity is still valuable.
• Going from 8 to 16 workers on an 8-core machine gives only 10-15% improvement. Workers start sharing CPU time rather than running in parallel.
• At 300 employees with 1 worker, the solver times out at 30 minutes without finding a good solution. With 8 workers, it converges in 15 minutes.

Impact of variable reduction

The benchmarks above use qualification and absence filtering. Without these optimisations, the 200-employee case with 8 workers takes 14-18 minutes instead of 8. The 300-employee case takes 22-28 minutes instead of 15. Variable reduction is not optional at scale.

Configuration recommendations

num_workers

Set num_workers equal to the number of physical CPU cores on your machine. On a cloud VM, this is usually 4 or 8. On a dedicated server, it may be 16 or 32. Do not exceed the physical core count.

import os
solver.parameters.num_workers = os.cpu_count()

Time limit

Match the time limit to the problem size and the use case:

Employees	Monthly generation	Interactive re-solve
< 150	5 minutes	2 minutes
150-200	15 minutes	5 minutes
200-300+	30 minutes	10 minutes

For monthly generation, quality matters more than speed. For interactive re-solves (after a manual edit), responsiveness matters more than the last 2% of optimality.

Logging

solver.parameters.log_search_progress = True

Always enable search logging during development. It shows the objective improvement over time, which workers are finding solutions, and the optimality gap. Disable it in production if log volume is a concern.

Model-level checklist

• Do not create assign[e, d, s] for unqualified employee-shift pairs
• Do not create assignment variables for absent employee-days
• Pre-compute toxic pairs for rest constraints
• Add symmetry-breaking constraints for interchangeable employees
• Use Boolean implications instead of big-M where possible
• Exclude absent employees from equity calculations

When to stop tuning

If the solver reaches an optimality gap under 5% within your time budget, further tuning will yield diminishing returns. Focus instead on the penalty structure: a well-calibrated objective function matters more than a 10% faster solve. The solver's job is to find the best schedule within the rules you define. Make sure the rules are right before optimising the search.