CBC vs CP-SAT: My Lineup Optimizer Got 8x Faster

Two months ago I wrote about CBC vs HiGHS on my staff scheduler, where swapping solvers turned a model that took minutes into one that took seconds. So when my daily fantasy lineup optimizer started feeling slow, I reached for the same fix — and HiGHS came back three times slower. This is the story of CBC vs CP-SAT on that model, why my own previous result did not transfer, and the failure mode I found on the way that was worse than being slow.

The model, in one paragraph

A single fantasy lineup is basically a knapsack problem: fill ten roster slots from a few hundred players, maximize projected points, stay under the salary cap. That part is easy. The interesting constraints are the ones on top — at least four hitters from one team, no hitters facing my own pitcher, a minimum number of distinct teams, and optionally that the stacked hitters occupy consecutive spots in the batting order, because adjacent batters score together.

Then there is the multiplier nobody thinks about until they build one of these: nobody wants one lineup, they want a hundred and fifty different ones. Twenty good lineups is the hard part, and the way I do it is to solve the model once per lineup, adding cuts each time so the next one cannot look too much like the ones already built. So every millisecond I save on a single solve gets paid back a hundred and fifty times. That is what makes solver choice worth an afternoon here.

HiGHS lost, and the reason is boring

I benchmarked on a real six-game DraftKings slate, roughly two hundred players after filtering out injured guys and pitchers who are not starting. Same options both ways, only the solver swapped:

CBC solves one of these lineups in about 0.14 seconds. When the actual solving takes that long, the per-call overhead of the Python API around the solver stops being a rounding error and starts being the whole bill. My scheduler model was genuinely hard — CBC took minutes on it — so a better branch-and-bound paid for itself many times over. A lineup is not hard. It is small, well-structured, and CBC eats it. The lesson I should have drawn the first time is that I was not learning something about HiGHS, I was learning something about that particular model.

CP-SAT, and the number that changed my mind

CP-SAT is the constraint-programming solver inside Google OR-Tools — a different animal from CBC, more SAT solver than simplex. It wants integer coefficients, so I scaled projections by a hundred, which is lossless at two decimals. Otherwise the model translated almost line for line. Same benchmark, with and without the consecutive batting-order rule turned on:

Two to three times faster on the plain configuration. Eight times faster with consecutive stacking on. Same top lineup to the decimal, so this is not a case of one solver quietly cutting corners — if anything CP-SAT’s totals across the whole batch came out slightly higher, because CBC kept bumping into its per-solve time limit and handing back answers it had not finished proving.

Why consecutive stacking is the breaking point

Notice that the gap widens exactly when I turn on the one feature that makes my optimizer different from the free ones. That is not a coincidence.

Forcing four stacked hitters into consecutive batting-order spots is written as a set of window variables — one binary per possible run of four, say slots 3 through 6 — plus implications tying each hitter’s selection to whichever window is active. That is reified logic: a constraint that only applies when some other variable is true. CP-SAT was built for exactly this; it reasons about implications directly. Branch-and-bound has to encode the same idea as inequalities, and the fractional relaxation it solves for guidance can satisfy them with half-selected players in half-active windows. The bound it computes is a fantasy, the same way it was on the scheduler, and the solver closes the gap the slow way.

The part that was worse than slow

The last row of that table says “never finished,” and that deserves more than a dash. My batch runner has a wall-clock budget: stop starting new solves after four minutes, return whatever you have. Running 150 lineups with consecutive stacking under CBC, that budget never fired. I killed the process at eleven minutes.

The budget is checked between solves, so it only works if each individual solve respects its own time limit. It did not. PuLP passes a time limit down to CBC, CBC accepts it, and on this class of model it sails past it anyway. One solve hung, and everything downstream — the batch cap, the streaming response, the whole request — hung behind it. In production that request would have sat there until the web server’s timeout killed it and the user got a half-written page.

So the honest framing is not “CP-SAT made my tool faster.” It is that my best feature was sitting on my least reliable code path, and I had not noticed because I had never run it at a hundred and fifty lineups. It is the same shape as the bug that only hung in production: the failure needed a scale I was not testing at.

Things I checked that did not pan out

Before rewriting anything I wanted to know where the time actually went, so I timed the model-building code separately from the solve call. Ninety-six percent was inside the solve. Building the model in Python was four percent. That killed my first theory, which was that PuLP writing an LP file to disk and shelling out to a CBC binary a hundred and fifty times was the problem. It is real overhead, but running CBC in-process through OR-Tools instead only bought about twenty percent — nowhere near enough to justify a rewrite on its own.

SCIP, also bundled with OR-Tools, came in twice as slow as CBC. And CP-SAT with four search workers was slower than CP-SAT with one, which surprised me until I remembered the model solves in a tenth of a second — there is not enough work to hand around. Worth knowing before you go shopping for CPUs expecting parallelism to save you.

What I would tell past me

Problem shape beats solver reputation. HiGHS is an excellent solver and it lost badly here. CBC is the one everybody dunks on and it beat HiGHS by three times on this model. CP-SAT won because a fantasy lineup is combinatorial rather than numerical — all binaries, integer coefficients, heavy logical structure — which is the terrain it was designed for. None of that is a ranking. It is a match between a model and a method.

Which means the only thing that generalizes is the habit: benchmark on your model, with the constraints you actually ship, at the size users actually run. Every number above changed depending on which options were on. If I had tested at twenty lineups without stacking I would have concluded CP-SAT was worth a modest 1.6x and probably not bothered.

Postscript: I tried the same swap on NFL

Having just written all that, I ported the NFL optimizer to CP-SAT too, expecting a smaller version of the same win. First measurement: five percent faster. Encouraging, so I nearly shipped it. Then I ran it four times instead of once.

CP-SAT is seventy percent slower on NFL, reliably, with identical lineups. My single-run “five percent faster” was noise — the machine varies by a third run to run, which is wider than the effect I thought I had found. If you take one practical thing from this post, take that: one run is not a measurement.

The reason fits everything above. MLB’s win came from consecutive batting-order stacking — window variables and implications, reified logic, CP-SAT’s home turf. Football has no such rule. What it has is one conditional stack requirement per quarterback and a pile of pairwise “don’t roster this defense against that offense” exclusions, and branch-and-bound handles those perfectly well. Same codebase, same two solvers, opposite answer.

So MLB runs on CP-SAT and NFL stays on CBC, each with the other path one environment variable away. That is a slightly embarrassing pair of sentences to write after a post arguing for a solver, and it is also exactly the point: I now have three models across two projects — a scheduler, a baseball lineup, a football lineup — and three different winners. If you want the solver’s own account of when constraint programming beats mixed-integer programming, Google’s CP-SAT documentation is unusually good on the question.

One caveat I owe you: every number here comes from one slate on one machine, timed by me, not from a solver benchmark suite. Different slate, different pool size, different options, different answers. That is rather the point.

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.