The Textbook Fix That Made My MILP Twice As Slow

The textbook move, when a mixed-integer program solves slowly, is to tighten the linear relaxation. Add the constraint that makes the LP bound closer to the integer optimum, give branch and bound less room to wander, watch it finish faster.

I did that to the stacking constraint in my hockey lineup optimizer last week. It got twice as slow. Same slate, same solver, same lineups out the other end — 2.20 seconds a lineup before, 4.38 after. I reverted it and left a comment telling future-me not to helpfully fix it again.

The model

A DraftKings NHL lineup is nine players under a $50,000 cap, filling two centre slots, three wing, two defence, a goalie and a utility. That part is a knapsack problem and it solves in milliseconds. The expensive part is stacking.

Hockey has natural correlated groups: a forward line is three players who take shifts together, a power-play unit is five who go out on the man advantage. A goal pays the scorer and up to two assists, so linemates tend to score together. “Stack two units, three players from each” is the core requirement, and expressing it is where the model gets hard.

The obvious formulation is a binary y per unit meaning “this unit is stacked”, and then:

sum(pick[i] for i in unit) >= 3 * y
sum(y for all units)       >= 2

Correct, and it relaxes terribly. The LP sets y = 1/3, buys a single player from the line, and declares the constraint satisfied at a third of the cost. Branch and bound gets no guidance from that bound whatsoever, so it explores, and on a twelve-team slate with 72 stackable units it spent its entire time limit on every single solve. 3.00 seconds a lineup, which on a 240-second budget is eighty lineups if nothing else goes wrong.

Cover inequalities, which did work

The fix is to say the same thing in a form the LP cannot cheat. If a unit has m members and you need k of them, then when y = 1 at most m − k members are left out. So every subset of size m − k + 1 must contain at least one rostered player:

for each subset S of size (m - k + 1):
    sum(pick[i] for i in S) >= y

For the common case — a three-man forward line stacked three deep — that collapses to pick[i] >= y for each of the three, which is exact and cannot be fractionally gamed. For a five-man power play stacked three deep it is ten subsets of three, which is still cheap. (I capped the subset count and skip the cuts above it, but on real NHL unit sizes the cap never fires.)

3.00 seconds a lineup down to 2.20. That is the single change that made the tool usable, and it is the textbook working exactly as advertised.

Then the textbook stopped working

The diversity rules need a second set of binaries: z per unit, meaning “two or more of this unit’s players are in this lineup”, so a later lineup can be told not to repeat it. I only wrote the upward implication — roster two, and z is forced on. Nothing rewards z, so the solver never sets it for free, and one direction is enough for correctness.

But it leaves the counter loose. The textbook tightening is to add the other side, so that a rostered line also forces its own indicator on, making z exact. Tighter relaxation, better bound, faster solve. That is the theory and I was confident enough that I nearly did not time it.

Measured, same slate, same preset, ten lineups: 2.20 seconds becomes 4.38. The tighter bound costs more than it saves — the extra rows are one per unit, 72 of them, on a model where CBC was already finishing, and it spends longer processing each node than the improved bound ever gives back. Same top lineup, same objective, twice the wall clock.

The thing I actually took from this: tighter is a means, not a goal. A relaxation is worth tightening when the search is thrashing, and worth leaving alone when it is not. I knew that in the abstract and still had to measure it to believe it.

Three solvers, and the answer flips by sport

With the cover cuts in, on the same slate:

CBC wins, which is awkward, because on the baseball version of this same codebase CP-SAT was eight times faster and I wrote a whole post about it. Both results are real. Baseball’s win came from consecutive batting-order stacking, which is built out of window binaries and implications — reified logic, CP-SAT’s home turf and branch-and-bound’s weak spot. Hockey has no constraint of that shape. What it has is a pile of cover cuts and cardinality rules, and CBC’s relaxation handles those perfectly well.

HiGHS being slowest is worth recording too, because HiGHS is the right answer in my staff scheduler, where CBC finished worse and called it optimal. The shape of the model decides, not the solver’s reputation. Four models into this project I have four different answers, and the only reliable method has been to run all three and time them.

The cost that is not in any single solve

Building twenty lineups is not twenty times building one, because each new lineup has to differ from all the ones before it. Every prior lineup contributes cuts to the next model: player overlap, shared units, core caps, cooldowns.

Measured across one batch on a twelve-team slate:

In baseball the same curve is flat, and I had a comment in the shared code saying so. It was true for baseball and wrong for hockey, which is the sort of note that quietly misleads you months later.

This is also where I found a real bug. The batch loop stopped whenever a solve came back empty — but “no lineup satisfies these rules” and “the solver hit its own time limit without finding one” are different things, and only the first is terminal. With a three-second per-solve limit the run quit at 32 lineups after 74 seconds of a 240-second budget. Two hundred and sixty-six seconds of compute, sitting there unused, because of one conflated status code. One retry at a longer limit before giving up: 32 becomes 75.

Things that did not help, so you do not have to try them

A relative MIP gap has now failed three times across this project. At 1% it bought nothing at all. At 2% it bought about 12% of the wall clock and lost the top lineup, 90.50 down to 89.40. It is exposed behind an environment variable and switched off, because a gap that quietly returns worse answers is the worst failure mode there is — nothing in the output looks wrong.

Trimming the player pool has now failed twice. It feels obviously right: fewer variables, faster solve. It is slower, measurably, both times — 619 players down to 281 took it from 2.13 to 2.56 seconds a lineup. Fewer cheap filler players means the salary window and the diversity caps bite harder, so branch and bound does more work on a smaller model. I have stopped proposing it.

And loosening the diversity settings, which is the advice the page itself used to give when a batch came up short, does almost nothing. Tested one control at a time, every single one moved the lineup count by under 8%, and half of them made it worse. The page now says that instead.

All of it is running at the free NHL lineup optimizer — built with PuLP and CBC, no signup, and the settings this post is about are all exposed rather than hidden behind a preset.

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.