Linear and Integer Programming for WFM

Linear and Integer Programming for WFM provides the mathematical foundation for workforce scheduling optimization. Linear programming (LP) and its integer extension (IP/MIP) form the backbone of every commercial WFM solver's scheduling engine, translating staffing requirements into mathematically optimal solutions.

Overview

Linear programming finds the optimal value of a linear objective function subject to linear constraints. Integer programming adds the requirement that some or all variables take integer values — essential in workforce management where you cannot assign 0.7 of an agent to a shift. Mixed-integer programming (MIP) combines continuous and integer variables, making it the workhorse formulation for production WFM scheduling.

Every time a WFM system generates a schedule, it solves some variant of a linear or integer program. The shift assignment problem, the break placement problem, the overtime allocation problem — all reduce to constrained optimization over linear objectives.

Mathematical Foundation

Linear Programming

A linear program takes the standard form:

$\min {\mathbf{𝐜}}^T\mathbf{𝐱}$

subject to:

$A\mathbf{𝐱}\ge \mathbf{𝐛},\mathbf{𝐱}\ge 0$

where:

• $\mathbf{𝐱}$ is the vector of decision variables (quantities to determine)
• $\mathbf{𝐜}$ is the objective coefficient vector (costs or values)
• $A$ is the constraint matrix (resource consumption rates)
• $\mathbf{𝐛}$ is the right-hand side vector (resource limits or requirements)

The feasible region — the set of all points satisfying the constraints — forms a convex polytope. The simplex method (Dantzig, 1947) exploits the fact that the optimal solution lies at a vertex of this polytope, moving along edges from vertex to vertex until no improvement exists.

The dual of every LP provides economic interpretation: dual variables represent the marginal value of relaxing each constraint by one unit. In WFM terms, the dual variable on a coverage constraint tells you exactly how much your objective improves if you add one more agent to that interval.

Integer Programming

Integer programming adds integrality constraints:

$\min {\mathbf{𝐜}}^T\mathbf{𝐱}$

subject to:

$A\mathbf{𝐱}\ge \mathbf{𝐛},\mathbf{𝐱}\ge 0,x_i\in \mathbb{\mathbb{Z}}\text{ for }i\in I$

This transforms the problem from polynomial-time solvable (LP) to NP-hard (IP). The feasible region is no longer convex — it is a discrete set of points within the LP polytope.

Why WFM needs integers: You cannot assign 0.7 of an agent to a 9:00 AM shift. Shift assignments are binary (0 or 1). Headcount is integer. Break slots are discrete. The LP relaxation might say "assign 2.3 agents to Shift A and 1.7 to Shift B" — meaningless in practice.

Branch-and-Bound

The dominant algorithm for solving IPs:

1. Solve the LP relaxation (drop integrality constraints). This gives a lower bound on the optimal IP value.
2. If the LP solution is integer-feasible, it is optimal. Stop.
3. Otherwise, select a fractional variable $x_i=f$ and branch: create two subproblems with $x_i\le \lfloor f\rfloor$ and $x_i\ge \lceil f\rceil$.
4. Solve each subproblem's LP relaxation. Prune branches whose LP bound exceeds the best known integer solution.
5. Repeat until all branches are pruned or solved.

The LP relaxation bound is critical: it tells you how close your best integer solution is to optimal. A MIP gap of 1% means your solution is within 1% of the theoretical best — often acceptable in WFM where forecast error dwarfs optimization gaps.

Cutting Planes

Cutting planes tighten the LP relaxation by adding inequalities that cut off fractional solutions without eliminating integer-feasible points. Modern solvers combine branch-and-bound with cutting planes in branch-and-cut algorithms, often solving problems with millions of variables.

WFM Applications

Shift Scheduling as Set-Covering IP

The classic WFM scheduling problem: given demand across intervals, select shifts (from a catalog) to cover demand at minimum cost.

$\min \sum _{j\in J}{c}_j{x}_j$

subject to:

$\sum _{j\in J}{a}_{ij}{x}_j\ge d_i\mathrm{\forall }i\in I$

$x_j\in {\mathbb{\mathbb{Z}}}_{\ge 0}\mathrm{\forall }j\in J$

where:

• $J$ = set of available shift types (e.g., 8:00-16:00, 9:00-17:00, ...)
• $I$ = set of intervals (48 half-hours in a day)
• $c_j$ = cost of shift $j$ (wage rate x hours)
• $a_{ij}$ = 1 if shift $j$ covers interval $i$, 0 otherwise
• $d_i$ = required staff in interval $i$
• $x_j$ = number of agents assigned shift $j$

This is an integer program because you need whole agents. The LP relaxation provides a lower bound on the minimum cost.

Staffing Optimization as LP

When computing net staffing requirements (before individual assignment), the problem can be an LP. Given Erlang-derived requirements per interval and productivity assumptions, minimize total paid hours subject to service level constraints. The continuous relaxation is valid here because you are computing aggregate FTE requirements, not individual assignments.

Break Assignment as Binary IP

For 150 agents with 30-minute lunch breaks across a 4-hour window:

$\min \sum _{i,k}{w}_{ik}\cdot y_{ik}$

subject to:

• Each agent gets exactly one break: $\sum _k{y}_{ik}=1\mathrm{\forall }i$
• Coverage maintained: ${\text{staff}}_k-\sum _i{y}_{ik}\ge {\text{req}}_k\mathrm{\forall }k$
• $y_{ik}\in \{0,1\}$

where $y_{ik}=1$ if agent $i$ takes break in slot $k$, and $w_{ik}$ penalizes deviation from preferred break times.

Overtime Allocation

Given understaffing across intervals and a pool of agents eligible for overtime, select the minimum-cost overtime assignments. Each agent has availability windows, maximum OT hours, and a cost rate (potentially 1.5x). This is a bounded binary/integer program with side constraints (max consecutive days, skill matching).

Solver Landscape

Solver	Type	License	WFM Relevance
Gurobi	Commercial	Proprietary	Fastest on most MIP benchmarks. Used by Verint, Calabrio internally.
IBM CPLEX	Commercial	Proprietary	Long history in OR. Strong on large LPs.
HiGHS	Open-source	MIT	Best open-source LP/MIP solver (2024). Viable for mid-scale WFM.
CBC (COIN-OR)	Open-source	EPL	Mature but slower. Good for prototyping.
Google OR-Tools	Open-source	Apache 2.0	Wraps multiple solvers. CP-SAT hybrid solver increasingly competitive.
SCIP	Academic	Apache 2.0	Research-grade. Constraint integer programming.

For production WFM: commercial solvers (Gurobi, CPLEX) solve scheduling problems 10-100x faster than open-source alternatives on large instances. For prototyping or small centers (< 50 agents), HiGHS or OR-Tools suffice.

Worked Example

Problem: Minimize staffing cost for a 100-seat contact center across 48 half-hour intervals (06:00-06:00). Shift catalog: 6 start times (06:00 through 11:00, every hour), 8-hour duration with 30-minute unpaid lunch at hour 4.5. Wage: $18/hour for early shifts (06:00-08:00 start), $16/hour otherwise.

Requirements (agents needed per interval, peak shown):

• 06:00-08:00: ramp from 12 to 35
• 08:00-12:00: plateau at 45-52
• 12:00-14:00: peak at 58-62
• 14:00-18:00: decline from 55 to 30
• 18:00-22:00: taper from 25 to 10
• 22:00-06:00: overnight minimum 5

Formulation:

Let $x_j$ = number of agents on shift $j$ (6 shifts, so $j=1,...,6$).

$\min 144x_1+144x_2+128x_3+128x_4+128x_5+128x_6$

(8 hours x $18 for early shifts, 8 hours x $16 for standard)

Subject to 48 coverage constraints of the form:

$\sum _{j:\text{shift }j\text{ covers interval }i}{x}_j\ge d_i\mathrm{\forall }i=1,...,48$

Plus integrality: $x_j\in {\mathbb{\mathbb{Z}}}_{\ge 0}$

Solution (via HiGHS):

• Shift 1 (06:00): 12 agents
• Shift 2 (07:00): 15 agents
• Shift 3 (08:00): 18 agents
• Shift 4 (09:00): 10 agents
• Shift 5 (10:00): 7 agents
• Shift 6 (11:00): 5 agents
• Total: 67 agents, daily cost: $8,128
• LP relaxation bound: $8,096 (MIP gap: 0.4%)
• The 0.4% gap confirms the integer solution is near-optimal.

Insight: The binding constraints are the peak intervals (12:00-14:00). The dual values on these constraints indicate that reducing peak demand by 1 agent saves approximately $128/day — informing decisions about call deflection or skill-based routing to level demand.

Maturity Model Position

Linear and integer programming capabilities map to the WFM Maturity Model:

• Level 2 (Developing): Using LP-based staffing calculators (Erlang + LP for multi-skill)
• Level 3 (Defined): MIP-based shift optimization with commercial solver
• Level 4 (Managed): Custom MIP formulations incorporating business-specific constraints
• Level 5 (Optimizing): Real-time re-optimization with warm-starts, decomposition methods for enterprise-scale

See Also

• Operations Research
• Column Generation for WFM Scheduling
• Constraint Programming for WFM
• Metaheuristics for Workforce Optimization
• Schedule Optimization
• Erlang C
• Multi-Skill Scheduling

References

• Dantzig, G.B. (1963). Linear Programming and Extensions. Princeton University Press.
• Wolsey, L.A. (1998). Integer Programming. Wiley.
• Ernst, A.T., Jiang, H., Krishnamoorthy, M., & Sier, D. (2004). "Staff scheduling and rostering: A review of applications, methods and models." European Journal of Operational Research, 153(1), 3-27.
• Ingels, J. & Maenhout, B. (2015). "The impact of overtime as a scheduling option on the quality of nurse rostering solutions." Omega, 56, 46-57.