CP-SAT Rostering › Visualizing CP-SAT Rostering
Michael BrenndoerferAugust 26, 202510 min read
Machine Learning from ScratchAll chapters Part 9 of 9Optimization
CP-SAT Rostering › Visualizing CP-SAT RosteringOne section · Sections in this chapter3 / 8 ↓
Sections in this chapter8
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 create visualizations to understand how CP-SAT rostering works in practice. We'll start by setting up the necessary libraries and creating a simple example.
Now let's create a simple rostering example to visualize the concepts:
In[8]:
Code# Create a simple rostering problem with guaranteed feasibility
# We construct a deterministic problem that ensures a solution exists
# NOTE: This section only sets up the problem parameters (availability, requirements).
# The actual solving is done later using the CP-SAT solver.
# Problem parameters
employees = ["Alice", "Bob", "Charlie", "Diana", "Eve"]
shifts = ["Morning", "Afternoon", "Evening", "Night"]
days = ["Mon", "Tue", "Wed", "Thu", "Fri", "Sat", "Sun"]
# Create availability matrix with very high availability to guarantee feasibility
# Start with all employees available for all shifts
np.random.seed(42)
availability = np.ones((len(employees), len(shifts), len(days)), dtype=int)
# Add minimal unavailability for realism, but ensure each shift-day
# has at least 4 available employees (more than we'll ever need)
for s in range(len(shifts)):
for d in range(len(days)):
# Allow at most 1 employee to be unavailable per shift-day
# This ensures at least 4 are available (we only need 1-2)
unavailable_count = np.random.choice([0, 1], p=[0.7, 0.3])
if unavailable_count > 0:
unavailable_idx = np.random.choice(len(employees))
availability[unavailable_idx, s, d] = 0
# Final check: ensure at least 4 are available
if availability[:, s, d].sum() < 4:
availability[:, s, d] = 1 # Reset to all available
# Then make at most 1 unavailable
unavailable_idx = np.random.choice(len(employees))
availability[unavailable_idx, s, d] = 0
# Set required staff conservatively to guarantee feasibility
# Strategy: require 1 per shift on most days, with some days having 0 for night/evening
# This ensures we have plenty of slack for the "no consecutive night shifts" constraint
# Total: 4 shifts × 7 days = 28 shift-days
# We'll require about 16-18 total assignments (well below 25 max possible)
required_staff = np.array(
[
[1, 1, 1, 1, 1, 1, 1], # Morning: 1 per day (7 total)
[1, 1, 1, 1, 1, 1, 1], # Afternoon: 1 per day (7 total)
[
1,
0,
1,
0,
1,
0,
1,
], # Evening: 1 on Mon, Wed, Fri, Sun (4 total, alternating)
[
0,
1,
0,
1,
0,
1,
0,
], # Night: 1 on Tue, Thu, Sat (3 total, no consecutive days)
]
)
# Total: 7 + 7 + 4 + 3 = 21 assignments required
# Max possible: 5 employees × 5 shifts = 25, so this is feasible
# Night shifts are on non-consecutive days, satisfying the constraint
# Verify feasibility: ensure each shift-day has enough available employees
for s in range(len(shifts)):
for d in range(len(days)):
available_count = availability[:, s, d].sum()
# If required exceeds available, reduce requirement
if required_staff[s, d] > available_count:
required_staff[s, d] = max(0, available_count)
# Ensure we have at least as many available as required
if required_staff[s, d] > 0 and available_count < required_staff[s, d]:
required_staff[s, d] = available_count
# Final verification: total required should be feasible
total_required = required_staff.sum()
max_possible = len(employees) * 5 # 5 max shifts per employee
if total_required > max_possible:
# Scale down proportionally, but keep it conservative
scale_factor = (
max_possible - 2
) / total_required # Leave 2 assignments buffer
required_staff = np.maximum(
0, np.round(required_staff * scale_factor).astype(int)
)
# Recalculate after scaling
total_required = required_staff.sum()In[9]:
Codeavailability_df = pd.DataFrame(
availability.reshape(len(employees), -1),
index=employees,
columns=[f"{shift}_{day}" for shift in shifts for day in days],
)In[10]:
Code# Display availability matrix
# Only the first 5 columns of the availability matrix
print(availability_df.iloc[:, :5])Out[10]:
ConsoleMorning_Mon Morning_Tue Morning_Wed Morning_Thu Morning_Fri Alice 1 1 1 1 1 Bob 1 1 1 1 1 Charlie 1 0 1 1 1 Diana 1 1 1 1 1 Eve 1 1 0 1 1
Understanding the rostering problem requires visualizing both employee availability and staffing requirements. These visualizations help identify potential scheduling challenges and ensure that the CP-SAT solver has sufficient information to find feasible solutions. The availability matrix reveals which employees can work specific shifts, while the staffing requirements define the minimum coverage needed for operations.
Out[11]:
Visualization
Now let's implement the CP-SAT model:
In[12]:
Code# Create CP-SAT model
model = cp_model.CpModel()
# Decision variables: x[employee][shift][day] = 1 if assigned, 0 otherwise
x = {}
for e in range(len(employees)):
for s in range(len(shifts)):
for d in range(len(days)):
x[e, s, d] = model.NewBoolVar(f"x_{e}_{s}_{d}")
# Coverage constraints: each shift must have required staff
for s in range(len(shifts)):
for d in range(len(days)):
model.Add(
sum(x[e, s, d] for e in range(len(employees)))
== required_staff[s, d]
)
# Availability constraints: employees can only be assigned if available
for e in range(len(employees)):
for s in range(len(shifts)):
for d in range(len(days)):
if availability[e, s, d] == 0:
model.Add(x[e, s, d] == 0)
# Maximum shifts per employee per week (limit to 5)
for e in range(len(employees)):
model.Add(
sum(x[e, s, d] for s in range(len(shifts)) for d in range(len(days)))
<= 5
)
# No consecutive night shifts
for e in range(len(employees)):
for d in range(len(days) - 1):
model.Add(x[e, 3, d] + x[e, 3, d + 1] <= 1) # Night shift is index 3The CP-SAT model has now been created with several key constraints:
- Coverage: Each shift must have exactly the required number of staff.
- Availability: Employees can only be assigned to shifts when they are available.
- Maximum shifts: No employee is assigned to more than 5 shifts per week.
- No consecutive night shifts: Employees are not scheduled for night shifts on back-to-back days.
Let's solve the model and visualize the results:
In[13]:
Code# Solve the model
solver = cp_model.CpSolver()
solver.parameters.random_seed = 42
solver.parameters.num_search_workers = 1
status = solver.Solve(model)
# Initialize solution array
solution = np.zeros((len(employees), len(shifts), len(days)))
if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
# Extract solution
for e in range(len(employees)):
for s in range(len(shifts)):
for d in range(len(days)):
if solver.Value(x[e, s, d]) == 1:
solution[e, s, d] = 1
# Ensure solution is integer type
solution = solution.astype(int)Out[14]:
ConsoleSolution Status: OPTIMAL Solution found! Total assignments: 21 Total required: 21 Solve time: 0.005 seconds ✓ All coverage requirements met
The CP-SAT solver's solution can be visualized to understand how the optimization process assigns employees to shifts. These visualizations reveal the final schedule structure and help assess the quality and fairness of the solution. The assignment matrix shows exactly which employees are scheduled for each shift, while the workload distribution chart helps evaluate whether the solution provides balanced assignments across all employees.
Out[15]:
Visualization
