CP-SAT Rostering › Formula

Rostering comes down to a series of yes-or-no questions: should Alice work the morning shift on Monday? Should Bob cover the night shift on Friday? Each of these questions demands a binary answer. There's no such thing as "half an assignment." This fundamental observation leads us directly to the mathematical structure that makes CP-SAT rostering effective for this type of problem.

Imagine you're a manager creating next week's schedule. For every possible combination of employee, shift type, and day, you face a simple decision: assign them or don't. There are no shades of gray. An employee either works a shift or they don't. This binary nature of rostering decisions is precisely what we capture mathematically.

We represent each possible assignment as a binary decision variable:

$$x_{e,s,t} \in \{0, 1\} \quad \forall e \in E, s \in S, t \in T$$

where:

• $E$: the set of all employees (indexed by $e$)
• $S$: the set of all shift types, such as Morning, Afternoon, Evening, or Night (indexed by $s$)
• $T$: the set of all time periods, typically days of the week (indexed by $t$)
• $x_{e,s,t}$: binary decision variable equal to 1 if employee $e$ is assigned to shift $s$ in time period $t$, and 0 otherwise

Why binary variables? Because rostering is inherently discrete. You cannot assign someone to "0.7 of a shift" or "part-time coverage." The binary representation forces our model to make clear, unambiguous decisions that match the reality of workforce scheduling. This mathematical choice isn't arbitrary. It directly reflects the nature of the problem we're solving.

Even a small roster produces an explosion of binary decisions. With 5 employees working across 4 shift types over 7 days, you're making $5 \times 4 \times 7 = 140$ independent yes-or-no decisions. Each decision variable can be either 0 or 1, giving a solution space with $2^{140}$ possible combinations. This is an astronomically large number that makes brute-force search completely impractical.

To visualize the structure of these decision variables, imagine a three-dimensional space whose dimensions represent the employee, shift type, and time period of an assignment. Each point in this space corresponds to a binary decision variable that can take the value 0 (not assigned) or 1 (assigned).

Having decision variables is just the beginning. Without rules, we could assign anyone to any shift at any time, but that would create chaos. Real-world rostering typically needs to satisfy multiple competing requirements simultaneously. These requirements become constraints in our mathematical model: rules that any valid solution should obey.

Think of constraints as the guardrails that keep our solution on track. They transform an impossibly large space of potential assignments into a manageable set of feasible solutions. Each constraint type addresses a different real-world concern, and together they ensure our roster is both operationally viable and legally compliant.

Coverage Constraints: The most fundamental requirement is that every shift should be staffed. Imagine a hospital emergency room that needs at least 3 nurses on the night shift, or a restaurant that requires 2 servers during dinner rush. Coverage constraints ensure we meet these minimum staffing levels:

$$\sum_{e \in E} x_{e,s,t} = r_{s,t} \quad \forall s \in S, t \in T$$

This formula says: for every shift type $s$ and every time period $t$, the sum of all assignments (where $x_{e,s,t} = 1$) should equal the required number of employees $r_{s,t}$. The summation $\sum_{e \in E}$ counts how many employees are assigned. We're adding up the ones. Why equality rather than "at least"? Because we can also model "exactly $r_{s,t}$ employees" if needed, though in practice you might use $\geq$ to allow overstaffing.

where:

• $r_{s,t}$: the minimum number of employees required for shift $s$ in time period $t$ (also called the staffing requirement)

This constraint is non-negotiable. If coverage isn't met, operations fail. But coverage alone isn't enough. We also need to respect the reality that employees have lives outside work.

Employee Availability: People can't work when they're unavailable. Alice might have classes on Tuesday mornings, Bob might be on vacation, or Charlie might have childcare responsibilities. Availability constraints prevent impossible assignments:

$$x_{e,s,t} = 0 \quad \forall (e,s,t) \in \mathcal{U}$$

where:

• $\mathcal{U}$: the set of all infeasible assignments $(e,s,t)$ where employee $e$ is unavailable for shift $s$ in period $t$ (a subset of $E \times S \times T$)

By setting $x_{e,s,t} = 0$ for all $(e,s,t) \in \mathcal{U}$, we're telling the solver: "These assignments are off-limits. Don't even consider them." This significantly reduces the search space and helps prevent schedules that violate employee availability. The constraint applies to each infeasible triple individually, effectively removing those decision variables from consideration.

Maximum Shifts per Employee: Fairness matters. We can't have one employee working 10 shifts while another works 2. Maximum shift constraints ensure balanced workloads:

$$\sum_{s \in S, t \in T} x_{e,s,t} \leq m_e \quad \forall e \in E$$

where:

• $m_e$: the maximum number of shifts employee $e$ can work during the planning period (a non-negative integer, typically set based on labor regulations or organizational policies)

The summation $\sum_{s \in S, t \in T} x_{e,s,t}$ counts all assignments for employee $e$ across all shifts and time periods. This sum equals the total number of shifts assigned to employee $e$ (since each $x_{e,s,t}$ is either 0 or 1). By requiring this sum to be $\leq m_e$, we cap each employee's total workload. This constraint prevents burnout and ensures compliance with labor regulations that limit working hours.

Rest Periods: Perhaps the most critical constraint for employee well-being is that people need rest. Working consecutive shifts without adequate recovery time is unsafe, illegal in many jurisdictions, and leads to poor performance. The rest period constraint prevents this:

$$x_{e,s_1,t} + x_{e,s_2,t + \Delta t} \leq 1 \quad \forall e \in E, \text{ where } \Delta t < \rho$$

where:

• $\Delta t$: the time gap between consecutive shifts (measured in the same units as $t$, typically hours or time periods)
• $\rho$: the minimum required rest period between shifts (often 8-12 hours, measured in the same units as $\Delta t$)
• $s_1, s_2$: two different shift types (the constraint applies to any pair of shifts)
• $t$: the time period of the first shift
• $t + \Delta t$: the time period of the second shift, occurring $\Delta t$ time units after the first

The constraint $x_{e,s_1,t} + x_{e,s_2,t + \Delta t} \leq 1$ works as follows: if an employee works shift $s_1$ at time $t$ (so $x_{e,s_1,t} = 1$), and the time gap $\Delta t$ is less than the minimum rest period $\rho$, then they cannot work shift $s_2$ at time $t + \Delta t$ (forcing $x_{e,s_2,t + \Delta t} = 0$). The sum of these two binary variables cannot exceed 1, meaning at most one of them can be 1. This mathematical relationship directly encodes the physical reality that people need time to rest.

The rest period constraint can be visualized as a timeline showing how consecutive shift assignments are restricted. When an employee works a shift at time $t$, they cannot work another shift at time $t + \Delta t$ if the time gap $\Delta t$ is less than the minimum rest period $\rho$.

Constraints tell us what's allowed, but they don't tell us what's best. Among all feasible solutions, and there may be thousands, which one should we choose? This is where the objective function comes in. It quantifies what "best" means for our specific situation.

Most commonly, we want to minimize costs. Every assignment has a cost: regular wages, overtime premiums, or penalties for assigning someone to an undesirable shift. The objective function sums these costs across all assignments:

$$\min \sum_{e \in E} \sum_{s \in S} \sum_{t \in T} c_{e,s,t} \cdot x_{e,s,t}$$

where:

• $c_{e,s,t}$: the cost of assigning employee $e$ to shift $s$ in period $t$ (a non-negative real number, typically measured in currency units or preference scores)

The binary nature of $x_{e,s,t}$ works well here: when $x_{e,s,t} = 0$ (no assignment), the term contributes nothing to the sum. When $x_{e,s,t} = 1$ (assignment made), the cost $c_{e,s,t}$ is added. The triple summation $\sum_{e \in E} \sum_{s \in S} \sum_{t \in T}$ ensures we consider every possible assignment, but only the ones that occur (where $x_{e,s,t} = 1$) contribute to the total cost.

The cost $c_{e,s,t}$ can encode various business priorities:

• Labor costs: Base wages for the shift
• Overtime premiums: Higher costs for shifts that push employees over their regular hours
• Preference penalties: Costs that discourage assigning employees to shifts they dislike
• Skill premiums: Costs that reflect the value of assigning highly skilled employees to critical shifts

By minimizing this sum, we find the schedule that satisfies all constraints while keeping total costs as low as possible. But cost isn't the only possible objective. We could maximize fairness, minimize schedule changes from previous periods, or balance multiple objectives simultaneously.

Now that we've built our mathematical model, let's understand the scale of the problem we're solving. The properties we'll explore explain why sophisticated algorithms like CP-SAT are necessary and why naive approaches fail spectacularly.

Solution Space Size: The combinatorial explosion

With $|E|$ employees, $|S|$ shift types, and $|T|$ time periods, we have $|E| \times |S| \times |T|$ binary decision variables. Each variable can independently be 0 or 1, which means the total number of possible assignments is:

$$|\mathcal{S}| = 2^{|E| \times |S| \times |T|}$$

where:

• $\mathcal{S}$: the set of all possible solutions (before applying constraints)
• $|E|$: the cardinality (size) of the employee set $E$, i.e., the number of employees
• $|S|$: the cardinality (size) of the shift type set $S$, i.e., the number of shift types
• $|T|$: the cardinality (size) of the time period set $T$, i.e., the number of time periods
• $|E| \times |S| \times |T|$: the total number of decision variables (the product of the three set sizes)

This exponential growth is the heart of the challenge. Consider a modest problem: 10 employees, 4 shift types, 7 days. That's $10 \times 4 \times 7 = 280$ decision variables, creating $2^{280} \approx 10^{84}$ possible solutions. To put this in perspective, there are estimated to be $10^{80}$ atoms in the observable universe. We're dealing with numbers so large that exhaustive enumeration is computationally infeasible. Even if we could check a billion solutions per second, it would take longer than the age of the universe to explore them all.

This is why constraints are so powerful: they eliminate vast swaths of this solution space. But even with constraints, the remaining feasible space can be enormous. We need algorithms that can intelligently search this space without exploring every possibility.

The exponential growth of the solution space can be visualized to understand why exhaustive search becomes infeasible even for moderately-sized problems. As the number of decision variables increases, the solution space grows at an exponential rate, making it computationally intractable to explore all possibilities.