Why We Chose CP-SAT Over MIP for Staff Rostering

Two paradigms for solving hard problems

When you need to solve a large-scale optimization problem, two families of solvers dominate the landscape: Mixed-Integer Programming (MIP) and Constraint Programming (CP). Both can solve employee scheduling problems. Both can handle hundreds of employees and thousands of variables. But they approach the problem from fundamentally different angles, and the choice matters.

MIP solvers like Gurobi and CPLEX come from the operations research tradition. They model problems as systems of linear inequalities and use linear relaxation combined with branch-and-bound to find optimal solutions. CP solvers like Google's CP-SAT come from the artificial intelligence and constraint satisfaction tradition. They use constraint propagation, SAT techniques, and lazy clause generation to explore the search space.

This article explains why we chose CP-SAT for employee scheduling, where each approach excels, and where MIP would be the better tool.

MIP: Mixed-Integer Programming

A MIP solver works by relaxing integer variables to continuous values, solving the resulting linear program (LP), and then using branch-and-bound to recover integer solutions. The LP relaxation provides a lower bound on the objective, which the solver uses to prune the search tree.

MIP strengths:

• Continuous variables are native. If your problem involves fractional quantities (cost allocation, resource flows, blending), MIP handles them directly. No discretization needed.
• Strong LP relaxation bounds. For problems with "tight" LP relaxations (transportation, network flow, facility location), the gap between the LP bound and the integer optimum is small. The solver can prove optimality quickly.
• Mature commercial solvers. Gurobi and CPLEX have decades of engineering behind them. They include presolve, cutting planes, heuristics, and parallel search. For well-structured LP/MIP problems, they are extremely fast.
• Dual bounds. MIP solvers provide a provable lower bound at every point during the search. You always know how far your current solution is from the theoretical optimum.

The canonical MIP formulation for scheduling uses 0/1 integer variables: x[e,d,s] = 1 if employee e works shift s on day d. Constraints are written as linear inequalities. The objective is a linear function of decision variables. This works, but scheduling introduces structure that MIP was not originally designed for.

CP-SAT: Constraint Programming with SAT

CP-SAT is Google's open-source solver from the OR-Tools library. It combines three techniques:

• Constraint propagation. When a variable is assigned or a domain is reduced, the solver immediately propagates the consequences through all connected constraints. This prunes impossible values before the search even considers them.
• SAT solving. The solver encodes the problem as a Boolean satisfiability problem and uses modern SAT techniques: conflict-driven clause learning (CDCL), restarts, and activity-based variable selection.
• Lazy clause generation (LCG). When the solver encounters a conflict, it generates a clause that explains the conflict and adds it to the clause database. This prevents the solver from revisiting the same dead end.

CP-SAT strengths:

• Boolean variables are first-class citizens. The variable assign[e,d,s] is naturally Boolean. No need to model it as a continuous variable relaxed to [0,1] and then rounded back to integer.
• Rich constraint types. CP-SAT natively supports AllDifferent, Circuit, Element, Automaton, Reservoir, and other global constraints. These encode complex combinatorial structures in a single constraint, with specialized propagation algorithms.
• Non-linear penalties. Objectives can include min/max expressions, absolute values, and conditional penalties without linearization tricks.
• Parallel diverse search. CP-SAT runs multiple search strategies (workers) simultaneously, each with different variable/value selection heuristics. This provides implicit diversification without manual tuning.

Scheduling is fundamentally combinatorial

The core decision in employee scheduling is: "Does employee e work shift s on day d?" This is a yes/no question. There is no meaningful "half-assignment" where an employee works 0.6 of a shift. The problem is inherently discrete and combinatorial.

In MIP, you model this as a 0/1 integer variable x[e,d,s]. The LP relaxation allows x[e,d,s] = 0.3, which has no physical meaning. The solver spends effort branching on these fractional values to recover integer solutions. For scheduling problems with many symmetries (employees with identical qualifications), the LP relaxation can be weak, meaning the bound is loose and the branch-and-bound tree is large.

In CP-SAT, assign[e,d,s] is a Boolean variable from the start. The solver never considers fractional assignments. When it decides that employee e works on day d, constraint propagation immediately removes conflicting shifts from consideration. This native handling of Boolean decisions is a structural advantage for scheduling.

Where CP-SAT excels for scheduling

Toxic pairs (minimum rest between shifts)

Labour regulations require 11 hours of rest between the end of one shift and the start of the next. We pre-compute "toxic pairs": shift combinations that would violate this rule.

# CP-SAT: Boolean implication, propagated instantly
assign[e, d, s1] + assign[e, d+1, s2] <= 1

In CP-SAT, this is a native Boolean implication. When assign[e,d,s1] is set to 1, the solver immediately propagates assign[e,d+1,s2] = 0. No branching needed. In MIP, the same constraint is written identically, but the LP relaxation allows both variables to be 0.5, providing no useful pruning until the solver branches on one of them.

Qualification enforcement

If an employee is not qualified for a shift, we simply do not create the assign variable for that combination. In CP-SAT, this is natural: the variable does not exist, so the solver never considers it. In MIP, you either fix the variable to 0 (adding explicit constraints) or omit it from the formulation (which MIP solvers can also do, but the propagation benefit in CP is stronger because it cascades through connected constraints).

Multi-objective with weighted penalties

Our objective function is a weighted sum of soft penalty terms: missing coverage (10,000 per slot), missing days off (1,500 per day), no weekend guaranteed (5,000), consecutive days violation (2,000), isolated days off (1,000), qualification equity gaps (500), workload equity gaps.

Each penalty involves conditional logic: "if the coverage on day d is below the target, penalize the shortfall." In CP-SAT, this is expressed directly using max(0, target - assigned) with no linearization. In MIP, you need auxiliary variables and big-M constraints to model the conditional structure, which can weaken the LP relaxation.

Symmetry handling

When multiple employees have the same qualifications and contract type, swapping their schedules produces an equivalent solution. This symmetry creates large plateaus in the search space where the solver makes no progress. CP-SAT's parallel diverse search, with workers using different heuristics and restart strategies, handles symmetry more effectively than MIP's branch-and-bound, which can get stuck exploring equivalent branches.

Where MIP is the better choice

Continuous optimization

If your problem involves minimizing a total cost function with fractional resource allocation, MIP is the natural choice. Blending problems, portfolio optimization, supply chain planning with continuous flows: these are MIP territory. CP-SAT works with integers and Booleans. If you need x = 3.7, you would have to scale and discretize.

Problems with strong LP relaxation

Transportation, minimum-cost flow, network design, facility location: these problems have LP relaxations that are tight. The LP bound is close to the integer optimum, and the branch-and-bound tree is small. MIP solvers exploit this structure brilliantly. For these problems, MIP is faster and provides better optimality guarantees.

When you need provable dual bounds

MIP solvers maintain a tight lower bound throughout the search. At any point, you know the gap between your best solution and the theoretical optimum. CP-SAT computes bounds too, but for problems with weak LP structure (which includes most scheduling problems), the CP-SAT bound can be looser. If proving optimality within a tight gap is critical, MIP's LP-based bounds are stronger.

Large-scale linear structure

If your problem is fundamentally a linear program with a few integer variables (e.g., "choose which 5 warehouses to open, then optimize continuous flows"), MIP solvers are unbeatable. The LP solver handles the continuous part efficiently, and branch-and-bound explores the small integer search space.

Licensing and cost

This is a practical concern that matters for on-premise deployment.

Solver	License	Cost	On-premise
CP-SAT (OR-Tools)	Apache 2.0	Free, forever	No restrictions
Gurobi	Commercial	Academic free, commercial from $12,000+/year	Requires license server
CPLEX	Commercial	Academic free, commercial similar to Gurobi	Requires license server
HiGHS	MIT	Free	No restrictions (LP/MIP only)
SCIP	Apache 2.0	Free	No restrictions

For an on-premise scheduling system deployed at client sites, licensing adds both cost and operational complexity. A Gurobi or CPLEX license needs to be provisioned, activated, and renewed for each deployment. With CP-SAT, the solver is bundled with the application. No license server, no activation, no renewal. The total cost of ownership is significantly lower.

Open-source also means no vendor lock-in. If Google were to abandon OR-Tools (unlikely given its widespread use), the Apache 2.0 license allows anyone to fork and maintain the project. With a commercial solver, you are dependent on the vendor's business decisions.

Our choice: CP-SAT for employee scheduling

For our use case, the decision was clear:

• The problem is combinatorial. Every decision variable is Boolean: employee e works shift s on day d, or not. CP-SAT handles Boolean variables natively.
• Constraints are complex. Toxic pairs, qualification enforcement, weekend guarantees, consecutive day limits: these translate directly into CP-SAT's constraint language without linearization.
• The objective is a weighted multi-penalty sum. Conditional penalties with different priorities. CP-SAT expresses these naturally.
• Deployment is on-premise. No license server, no per-seat cost, no vendor dependency. CP-SAT ships with the application.
• Performance is sufficient. For 300 employees, 50 shift types, and 30 days, CP-SAT finds a good solution in under 5 minutes and converges to near-optimal in 15-30 minutes on an 8-core server.

Comparison summary

Dimension	CP-SAT	Gurobi	CPLEX
Variable types	Boolean, integer	Continuous, integer, Boolean	Continuous, integer, Boolean
Constraint types	AllDifferent, Circuit, Element, Automaton, Boolean implications	Linear inequalities, indicator constraints, SOS	Linear inequalities, indicator constraints, SOS
Licensing	Apache 2.0, free	Commercial, $12k+/year	Commercial, similar
Scheduling fit	Excellent: native Boolean, fast propagation	Good: requires linearization of some constraints	Good: requires linearization of some constraints
Continuous optimization	Not supported	Excellent	Excellent
LP bounds	Weaker for scheduling	Strong	Strong
Parallel search	Built-in diverse workers	Built-in parallel B&B	Built-in parallel B&B
Learning curve	Moderate (Python API)	Moderate (Python/C++ API)	Moderate (Python/C++ API)
Community	Open-source, active GitHub	Commercial support	Commercial support
On-premise deployment	No restrictions	License server required	License server required

If our problem were cost minimization with continuous flows, or network design with strong LP structure, we would choose Gurobi or CPLEX without hesitation. They are outstanding tools for the problems they were built for. But employee scheduling is a combinatorial problem with Boolean decisions, complex constraints, and multi-objective penalties. For this problem, CP-SAT is the better fit.