My generalized staff scheduler is a small optimization problem: eight people, a week of half-hour slots, about five thousand binary variables. By modern standards that is tiny. So when it started taking minutes to solve — or worse, returning nothing at all — my first reaction was disbelief. This post is the story of CBC vs HiGHS on that exact model, and the four fixes that actually mattered. If your PuLP + CBC model is grinding, some of these will probably apply to you too.
The LP relaxation lies
Branch-and-bound solvers work by solving a relaxed version of your problem first — same constraints, but variables are allowed to be fractional — and using it as an optimistic bound. My model solves that relaxation in under a second. The trouble is what the relaxation says. Fractionally, the solver can put 0.4 of John on the phones at 9:00 and the other 0.6 of him at 2:00, and my break-structure constraints — first and last slot of the day, one break, minimum block lengths, written in the classic big-M style — barely notice. Fractional solutions slide right through them.
So the bound is a fantasy, far below any real schedule’s cost, and the solver has to close that gap the hard way: branching. And because half my staff are near-interchangeable (same cost, similar availability), the search tree is full of schedules that are different on paper and identical in cost. CBC dutifully visits them all. Small model, enormous tree.
When finding any schedule is the hard part
The genuinely surprising failure was CBC returning no solution at all — not a bad schedule, none. The culprit was a stack of hard minimums: minimum hours per day, days per week, hours per week, on top of the break rules. Satisfying all of them at once is a puzzle, and CBC’s primal heuristics could not crack it within the time limit. Relax any single class of minimums and it solved in seconds; all three together and it starved.
The fix was to make the minimums elastic: a penalized shortfall instead of a wall. Feasibility becomes trivial (an empty schedule is legal, just expensive), the solver always has somewhere to start, and the user gets “Riley is 1 hour below his Tuesday minimum” instead of INFEASIBLE. Better math and better manners.
Two gotchas from the trenches
First: when CBC hits its time limit without an integer solution, PuLP hands you the fractional LP values as if they were variable values. If you read them naively you will report a “schedule” where people work half-slots and every rule is violated. Check integrality before trusting anything at a time limit — and conversely, if the incumbent IS integral, keep it; for a while my code was throwing away perfectly valid schedules just because the gap wasn’t proven.
Second, and I flag this one as a strong suspicion rather than a proven fact: passing the threads option to the CBC binary that ships with PuLP on Windows coincided with the solver blowing straight past its time limit. Removing the option restored sane behavior. If your time limits are being ignored on Windows, try dropping threads first.
Enter HiGHS
HiGHS is the current state of the art in open-source MILP solving, and PuLP supports it as a drop-in: pip install highspy, swap the solver object, done. On my worst-case configuration — the one where CBC found nothing in 30+ seconds — HiGHS proved optimality in 31 seconds. On the everyday configurations it solves the same models in 2 to 12 seconds. My engine now auto-detects it and falls back to CBC when it isn’t installed, printing which solver ran so nobody has to guess.
What I’d tell past me
In order of impact: model structure beat solver tuning — the elastic minimums and one structural pruning trick (auto-raising minimum block lengths to half a person’s longest stretch, which also centers breaks) did more than any parameter ever did. An optimality gap of a couple percent is your friend on lumpy objectives. Validate what the solver hands back at a time limit. And when the free solver you started with grinds, try the other free solver before you conclude your problem is hard — the CBC vs HiGHS difference on this model was the difference between “broken” and “instant.” The generalized scheduler this all came from is the subject of its own post, and the older one-client version is still live at staff-scheduling.kindoflost.com.
Things that I use, like, and am affiliated with:
Mint Mobile offers great cell phone service for $15 flat, get $15 off using the link. Get discounted phones with service activation and no contract.
I never spend money before I check Mr Rebates or Rakuten to get cashbacks, rebates, discounts, coupons or cheaper gift cards.