Column Generation for WFM Scheduling

Column Generation for WFM Scheduling solves large-scale shift scheduling problems where the number of feasible shifts is too large to enumerate explicitly. By dynamically generating only those shifts that can improve the current solution, column generation makes otherwise intractable scheduling problems solvable in practice.

Overview

A contact center operating 24/7 with shift starts every 15 minutes and shift lengths from 4 to 10 hours (in 15-minute increments) has over 2,400 possible shift definitions — before considering break placements, which multiply the count by orders of magnitude. A multi-day roster problem with weekly pattern variations can have millions of feasible columns. Explicit enumeration is impossible.

Column generation decomposes the problem: a master problem selects from a (small) subset of columns, while a pricing subproblem generates new columns that can improve the objective. The algorithm iterates between solving the master and generating columns until no improving column exists.

Every major commercial WFM scheduling engine — NICE, Verint, Calabrio, Genesys — uses some form of column generation internally for shift optimization. Understanding the mechanism explains why WFM solvers behave as they do: why they sometimes find excellent solutions quickly and other times struggle with specific constraint combinations.

Mathematical Foundation

Dantzig-Wolfe Decomposition

Column generation originates from Dantzig-Wolfe decomposition (1960). The insight: many optimization problems have a block-diagonal structure with linking constraints. Rather than solving the monolithic problem, decompose it into a master problem (linking constraints) and subproblems (block structure).

For WFM scheduling, the linking constraints are interval coverage requirements — the demand that must be met in each time period. The block structure is the shift feasibility rules — labor laws, contract terms, break policies that define what constitutes a valid shift.

The Master Problem

The restricted master problem (RMP) is a set-covering formulation over a subset of feasible shifts:

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

subject to:

$\sum _{j\in J^{\prime }}{a}_{ij}{x}_j\ge d_i\mathrm{\forall }i\in I({\pi }_i)$

$x_j\ge 0\mathrm{\forall }j\in J^{\prime }$

where $J^{\prime }\subset J$ is the current (restricted) set of shifts, and ${\pi }_i$ are the dual variables on the coverage constraints.

The Pricing Subproblem

After solving the RMP, we obtain dual values ${\pi }_i$ for each interval constraint. A new column (shift) $j$ improves the solution if and only if its reduced cost is negative:

${\overline{c}}_j=c_j-\sum _{i\in I}{\pi }_i{a}_{ij}<0$

The pricing subproblem finds the shift with minimum reduced cost:

$\underset{j\in J}{\min }(c_j-\sum _{i\in I}{\pi }_i{a}_{ij})$

subject to: shift $j$ satisfies all feasibility rules (start time, length, break placement, etc.)

This is typically a shortest path problem on a time-indexed network where:

• Nodes represent time points (every 15 minutes)
• Arcs represent work segments and break segments
• Arc costs incorporate the dual values ${\pi }_i$
• Path constraints enforce break timing, minimum/maximum work segments, etc.

The Column Generation Algorithm

1. Initialize $J^{\prime }$ with a small set of feasible shifts (or artificial variables)
2. Solve RMP: Obtain primal solution $x^{*}$ and dual values ${\pi }^{*}$
3. Solve pricing: Find minimum reduced cost shift. If ${\overline{c}}^{*}\ge 0$, the current solution is optimal for the LP relaxation. Stop.
4. Add column: Add the generated shift to $J^{\prime }$. Return to step 2.

Convergence is guaranteed because each iteration either adds an improving column or proves optimality. In practice, multiple columns per iteration (the k best) accelerates convergence.

Branch-and-Price

Column generation solves the LP relaxation. To obtain integer solutions, embed column generation within branch-and-bound — called branch-and-price. Branching decisions must be compatible with the pricing subproblem:

• Branch on shift assignment: Fix $x_j=0$ or $x_j\ge 1$ for a specific shift
• Branch on coverage: Require exactly $k$ agents in an interval (Ryan-Foster branching)
• Branch on agent-interval: Agent $i$ works/does not work interval $t$

Ryan-Foster branching is preferred in crew scheduling because it modifies the pricing subproblem minimally — only adjusting arc availability rather than changing the network structure.

LP Relaxation Quality

Column generation with set-covering formulations typically yields tight LP bounds — the gap between the LP relaxation and the integer optimum is small (often < 2% for WFM scheduling). This means:

• Simple rounding of the LP solution often gives good integer solutions
• Branch-and-price trees remain shallow
• Solution quality guarantees are strong

WFM Applications

Continuous Shift-Start Scheduling

When labor agreements permit shift starts at any 15-minute increment (rather than fixed start times), the shift catalog explodes. A center open 06:00-22:00 with 4-10 hour shifts starting every 15 minutes: 64 start times x 25 lengths = 1,600 shifts — before breaks. Column generation handles this naturally: the pricing subproblem generates only shifts that the current dual values indicate are useful.

Multi-Break Shift Construction

An 8-hour shift with one 30-minute lunch and two 15-minute breaks has hundreds of feasible break placements (depending on minimum work segment rules). For 150 agents, pre-enumerating all shift+break combinations is infeasible. The pricing subproblem constructs the optimal break placement for each shift as part of generating the column.

Weekly Roster Generation

A column in weekly rostering represents an entire week pattern for one agent: which days on/off, which shift each day. With 5 working days from 7, multiple shift types per day, and rest constraints between days — the column count is astronomical. Column generation iteratively builds rosters one agent-week at a time.

Multi-Skill Scheduling

When agents have different skill sets, the coverage constraints are per-skill-per-interval. A column represents not just a shift but a shift+skill assignment. The pricing subproblem must respect skill qualifications while optimizing against per-skill dual values — which solver uses which agent for which skill in which interval.

How Commercial WFM Solvers Use Column Generation

Commercial engines typically:

1. Use column generation for the macro scheduling phase (shift selection and headcount allocation)
2. Follow with a micro scheduling phase (break placement, activity assignment) using IP or constraint programming
3. Apply heuristic acceleration — generating multiple columns per iteration, warm-starting with the previous day's solution
4. Implement time limits with early termination — returning the best solution found when the optimization budget expires (often 2-5 minutes for daily regeneration)

Worked Example

Problem: Generate optimal shifts for a 24/7 contact center. Shift starts every 15 minutes. Lengths: 4, 5, 6, 7, 8, 9, 10 hours. One 30-minute unpaid break for shifts >= 6 hours. 96 intervals (15-minute). Peak demand: 85 agents (11:00-13:00). Overnight minimum: 8 agents. Wage: $17/hour base, $2/hour premium for night (22:00-06:00).

Shift catalog size: 96 start times x 7 lengths = 672 base shifts. With break placement (every 15 minutes in the middle third of the shift): approximately 672 x 8 average break positions = 5,376 columns for shifts with breaks. Total feasible columns: approximately 4,500 (after filtering infeasible break placements).

Column generation approach:

Initialization: Seed with 24 shifts (one 8-hour shift starting each hour). Artificial variables ensure feasibility.

Iteration 1:

• RMP solution with 24 shifts: cost $42,800/day, many intervals over/understaffed
• Dual values ${\pi }_i$ range from $0 (overstaffed intervals) to $38 (peak intervals)
• Pricing subproblem finds shift 09:15-17:15 with break at 12:30 — reduced cost -$52

Iteration 2-15:

• Each iteration adds 5-10 improving columns
• Objective drops: $42,800 → $38,200 → $36,500 → ... → $33,850

Iteration 23 (convergence):

• No negative reduced cost column exists
• LP optimal: $33,720/day using 142.3 agents (fractional)
• Active columns: 87 distinct shifts (from 4,500 possible)

Branch-and-price:

• Round LP solution: 144 agents, cost $33,890
• Branch-and-price optimal: 143 agents, cost $33,780
• Gap from LP bound: 0.18%

Key insight: Only 87 of 4,500 possible shifts appear in the optimal solution. Column generation found these 87 without evaluating the other 4,413. The dual values guided the search — high duals during peak drove generation of peak-covering shifts, low overnight duals meant few overnight shift variants were generated.

Result breakdown:

• Morning peak coverage (08:00-12:00): 23 distinct shift types active
• Afternoon (12:00-18:00): 19 shift types
• Evening (18:00-22:00): 15 shift types
• Overnight (22:00-06:00): 8 shift types (longer shifts preferred for premium pay efficiency)
• Short shifts (4-5 hours): concentrated around 11:00-14:00 peak fill

Maturity Model Position

Column generation capabilities map to the WFM Maturity Model:

• Level 3 (Defined): Using WFM solver's built-in column generation (may not realize it)
• Level 4 (Managed): Understanding solver behavior, tuning shift rule parameters to help the pricing subproblem, interpreting dual values for capacity planning
• Level 5 (Optimizing): Custom column generation implementations for non-standard problems, decomposition strategies for enterprise-scale multi-site optimization

See Also

• Linear and Integer Programming for WFM
• Constraint Programming for WFM
• Schedule Optimization
• Operations Research
• Shift Bidding and Preferences
• Multi-Skill Scheduling

References

• Dantzig, G.B. & Wolfe, P. (1960). "Decomposition principle for linear programs." Operations Research, 8(1), 101-111.
• Desrosiers, J. & Lubbecke, M.E. (2005). "A primer in column generation." In Column Generation, Springer, 1-32.
• Caprara, A., Monaci, M., & Toth, P. (2003). "Models and algorithms for a staff scheduling problem." Mathematical Programming, 98(1-3), 445-476.
• Van den Bergh, J., Beliën, J., De Bruecker, P., Demeulemeester, E., & De Boeck, L. (2013). "Personnel scheduling: A literature review." European Journal of Operational Research, 226(3), 367-385.
• Lubbecke, M.E. & Desrosiers, J. (2005). "Selected topics in column generation." Operations Research, 53(6), 1007-1023.