Building a high school or middle school schedule is a deceptively difficult problem. A school assigns hundreds or thousands of students to course sections while simultaneously scheduling teachers and classrooms over periods, days and terms. Students have individual course requests. Teachers and rooms have limited availability. Sections have capacity limits. Courses may meet on different combinations of days and periods. The final schedule must leave enough flexibility for administrators to adjust.
A technology platform startup company uses optimization to manage this challenge. Its optimization model seeks to assign students to appropriate sections in every period and term, satisfy student requests, create complete schedules for every student, assign sections to rooms, balance enrollment among equivalent sections, and preserve enough capacity to make the resulting schedule operationally workable.
The model worked successfully for many schools in different states. As the customer base and scheduling requirements grew, difficult instances yielded prohibitively long solve times. The desired runtime was less than one hour. For certain schools with complex requirements, it was not clear if a reasonable schedule meeting all requirements was possible within that time limit.
At the same time, the company needed the model to become more robust and adaptable. Schools continually introduce requirements that the scheduling platform must accommodate, such as new types of partial enrollment or specialized staff scheduling. The company’s technical team had substantial mathematical and software expertise but sought assistance to improve the optimization architecture and its performance. Leadership engaged Princeton Consultants to help determine how far the existing optimization approach could be improved and whether the problem needed to be formulated differently.
An Increasingly Difficult Combinatorial Problem
School scheduling belongs to a class of optimization problems in which apparently modest increases in requirements can dramatically increase computational difficulty. The model cannot build a master timetable and stop. It must consider the interactions between course schedules and individual students’ ability to enroll in the courses they request, along with staff and room considerations. A decision that looks attractive for one course may make it impossible for a group of students to complete their schedules. Likewise, maximizing enrollment in individual sections can produce a schedule with insufficient spare capacity for administrators to accommodate changes later.
These interdependencies create an enormous number of possible combinations. The company had already developed an optimization model, which solved most scheduling problems successfully, but performance was inconsistent on the hardest instances. This distinction mattered commercially: an optimization-based scheduling product needs to perform reliably across a heterogeneous customer base, including the schools whose combinations of course patterns, student requests and constraints produce especially difficult mathematical problems.
Stress-Testing the Existing Optimization Approach
Our team interviewed the company’s subject-matter experts, reviewed the existing formulation and documentation, studied previously attempted performance improvements, and assessed the model in its production context. That work led to a new formulation that removed some of the underlying combinatorial complexity. The company implemented the formulation, after which our team reviewed the resulting code and recommended implementation improvements.
We then investigated avenues for improving performance. Among them were simplifying multiple objectives, using lazy constraints, decomposing the problem by student grade, separating class scheduling from student scheduling, identifying periods in which students could not feasibly be scheduled, strengthening constraints for multi-day courses, grouping students with identical high-priority course requests, removing room-assignment variables and constraints to isolate computational bottlenecks, and relaxing enrollment limits to understand their effect on difficulty.
This experimentation generated incremental improvements and a deeper understanding of what made the hardest scheduling instances difficult.
Changing the Mathematical Architecture
Initial changes produced modest performance gains, and our team continued to support the company during its busy school-scheduling season, including work on high-level control of the Gurobi solver to balance efficiency and robustness. For the most difficult problems, however, solve times and solution quality still did not meet the company leaders’ objectives.
We proposed a formulation based on column generation techniques so that the scheduling problem could be represented in a way that gave the solver a substantially more efficient search space. (This formulation was made possible by our previous Reciprocal Integer Programming solution development work for Birchbox, which was recognized for its innovation and effectiveness as a finalist for the INFORMS Wagner Prize and is described in this article.) In the existing approach, the optimization model effectively had to reason about individual scheduling decisions involving days and periods. In the new approach, combinations of days and periods on which a course could be scheduled would be generated as complete patterns. The optimizer could then choose among feasible patterns for each course instead of constructing those patterns from individual day-and-period decisions.
Column generation (I recommend this classic overview) is an advanced optimization technique designed for problems in which explicitly representing every possible decision can create an unwieldy model. Instead of presenting the optimizer with the entire universe of possibilities at once, the technique works with useful combinations of decisions and generates additional possibilities as needed. The approach has been successfully applied to other complex optimization problems, such as airline crew scheduling.
Our team designed and implemented the reformulated model, documented the new mathematical formulation, reviewed the required input and output structures, and provided model code for the new approach. We continued to enhance the column-generation model and support its movement toward production. The next phase addressed additional scheduling requirements such as partial availability for support staff and links between sections in following periods. Our team provided troubleshooting and advisory support as the company integrated the new approach into its production environment.
Turning an Excellent Product Into a More Scalable One
For software companies whose products depend on optimization, the optimization model is often the most strategically important component of the technology platform. As products mature, their optimization requirements typically become harder, as customers request additional capabilities, business rules accumulate, problem sizes grow, and edge cases emerge. A formulation that performed well during an earlier stage of product development may eventually encounter computational limits. As it continues to leverage specialized optimization expertise and techniques, the company is boosting its scheduling services for a broader client base and expanding into new markets.
To discuss this with Irv Lustig and Patricia Randall, contact us to set up a call.
