CP-SAT Rostering › Implementation
Machine Learning from ScratchAll chapters CP-SAT Rostering › ImplementationOne section · Sections in this chapter4 / 8 ↓
Reading tools Definitions & inline links
Choose your expertise level to adjust how many terms are explained. Beginners see more tooltips, experts see fewer to maintain reading flow. Hover over underlined terms for instant definitions.
Article links
Make inline references clickable
Let's work through a detailed implementation to understand how CP-SAT rostering works step by step. We'll create a small problem with 3 employees, 2 shifts, and 3 days to make the calculations manageable and easy to follow.
Step 1: Problem Setup
First, we define the employees and shift types across the scheduling period. These parameters create the foundation for our rostering problem:
# Problem setup
employees_ex = ["Alice", "Bob", "Charlie"]
shifts_ex = ["Day", "Night"]
days_ex = ["Monday", "Tuesday", "Wednesday"]
# Employee availability matrix
availability_ex = np.array(
[
# Alice: available for Day shifts Mon-Wed, Night shift only Mon
[[1, 1, 1], [1, 0, 0]],
# Bob: available for Day shifts Mon-Tue, Night shifts Tue-Wed
[[1, 1, 0], [0, 1, 1]],
# Charlie: available for all Day shifts, Night shifts Mon and Wed
[[1, 1, 1], [1, 0, 1]],
]
)
# Required staff
required_ex = np.array(
[
[2, 2, 1], # Day shift needs 2, 2, 1 staff
[1, 1, 1], # Night shift needs 1, 1, 1 staff
]
)=== CP-SAT Rostering Example === Problem Setup: Employees: ['Alice', 'Bob', 'Charlie'] Shifts: ['Day', 'Night'] Days: ['Monday', 'Tuesday', 'Wednesday'] Employee Availability: Alice: Day: Monday, Tuesday, Wednesday Night: Monday Bob: Day: Monday, Tuesday Night: Tuesday, Wednesday Charlie: Day: Monday, Tuesday, Wednesday Night: Monday, Wednesday Required Staff: Monday Day: 2 staff Tuesday Day: 2 staff Wednesday Day: 1 staff Monday Night: 1 staff Tuesday Night: 1 staff Wednesday Night: 1 staff
The problem setup includes 3 employees, 2 shift types, and 3 days, creating 18 decision variables (3 × 2 × 3). The availability matrix reveals which employees can work specific shifts. For example, Alice is available for all Day shifts but only Monday Night shift. The required staff matrix shows our coverage targets, with Day shifts needing 2, 2, and 1 staff across the three days, and Night shifts each needing 1 staff member. This foundation provides sufficient employees and reasonable availability patterns to find a feasible solution.
Step 2: Model Construction
Now we build the CP-SAT model step by step. This involves creating the mathematical model and adding constraints that represent our business rules.
# Create CP-SAT model for example
model_ex = cp_model.CpModel()
# Decision variables
x_ex = {}
for e in range(len(employees_ex)):
for s in range(len(shifts_ex)):
for d in range(len(days_ex)):
x_ex[e, s, d] = model_ex.NewBoolVar(
f"x_{employees_ex[e]}_{shifts_ex[s]}_{days_ex[d]}"
)Adding Coverage Constraints: These ensure each shift has the required number of staff. This is an important constraint as it directly affects operational requirements:
# Coverage constraints - ensure each shift has required staff
for s in range(len(shifts_ex)):
for d in range(len(days_ex)):
constraint = sum(x_ex[e, s, d] for e in range(len(employees_ex)))
model_ex.Add(constraint == required_ex[s, d])Adding Availability Constraints: These respect employee schedules and prevent assignments when employees are unavailable:
# Availability constraints - respect employee schedules
for e in range(len(employees_ex)):
for s in range(len(shifts_ex)):
for d in range(len(days_ex)):
if availability_ex[e, s, d] == 0:
model_ex.Add(x_ex[e, s, d] == 0)Adding Workload Constraints: These limit the maximum number of shifts per employee to ensure fair workload distribution:
# Maximum shifts constraint - limit workload per employee
for e in range(len(employees_ex)):
total_shifts = sum(
x_ex[e, s, d]
for s in range(len(shifts_ex))
for d in range(len(days_ex))
)
model_ex.Add(total_shifts <= 3)Creating decision variables... Created 18 binary decision variables Adding coverage constraints... Monday Day: sum of assignments == 2 Tuesday Day: sum of assignments == 2 Wednesday Day: sum of assignments == 1 Monday Night: sum of assignments == 1 Tuesday Night: sum of assignments == 1 Wednesday Night: sum of assignments == 1 Adding availability constraints... Alice not available for Tuesday Night Alice not available for Wednesday Night Bob not available for Wednesday Day Bob not available for Monday Night Charlie not available for Tuesday Night Adding maximum shifts constraint... Alice: total shifts <= 3 Bob: total shifts <= 3 Charlie: total shifts <= 3
The model construction creates 18 binary decision variables (one for each employee-shift-day combination) and adds constraints that encode our business rules. The coverage constraints ensure each shift meets staffing requirements. For example, Monday Day shift must have exactly 2 employees assigned. The availability constraints prevent impossible assignments, such as Bob working Tuesday Day shift when he's unavailable. The maximum shifts constraint limits each employee to at most 3 shifts during the 3-day period. Together, these constraints define the feasible solution space that the solver will search.
Step 3: Model Solving
Now we solve the model and extract the solution. This is where the CP-SAT solver finds assignments that satisfy all our constraints:
# Solve the model
solver_ex = cp_model.CpSolver()
solver_ex.parameters.log_search_progress = True
solver_ex.parameters.random_seed = 42
solver_ex.parameters.num_search_workers = 1
status_ex = solver_ex.Solve(model_ex)
# Initialize solution array
solution_ex = np.zeros((len(employees_ex), len(shifts_ex), len(days_ex)))
# Extract solution if feasible
if status_ex == cp_model.OPTIMAL or status_ex == cp_model.FEASIBLE:
for e in range(len(employees_ex)):
for s in range(len(shifts_ex)):
for d in range(len(days_ex)):
if solver_ex.Value(x_ex[e, s, d]) == 1:
solution_ex[e, s, d] = 1
# Ensure solution is integer type
solution_ex = solution_ex.astype(int)Solving the model... Solution status: OPTIMAL Solve time: 0.00 seconds === SOLUTION === ✓ Alice assigned to Wednesday Day ✓ Alice assigned to Monday Night ✓ Bob assigned to Monday Day ✓ Bob assigned to Tuesday Day ✓ Bob assigned to Tuesday Night ✓ Charlie assigned to Monday Day ✓ Charlie assigned to Tuesday Day ✓ Charlie assigned to Wednesday Night Solution Summary: Monday: Day: Bob, Charlie Night: Alice Tuesday: Day: Bob, Charlie Night: Bob Wednesday: Day: Alice Night: Charlie Total assignments: 8 Required assignments: 8
The solver successfully found a feasible solution that satisfies all constraints. The solve time is typically under 0.1 seconds for small problems like this one, which indicates good performance. The solution shows that all required shifts are covered while respecting employee availability and workload limits. The total assignments match the required assignments, confirming that coverage constraints are satisfied. This result demonstrates that the assignment meets the coverage and availability requirements without exceeding maximum shift limits.