Personal blog on early retirement, a little traveling, and analytics projects. I write about what I learn as I am learning it.
My NHL lineup optimizer used to build every lineup the same way: hand the whole problem to a solver and wait. It now skips the solver for most of the work. It lists the stacks that are allowed, scores them, and picks the best one, and it does that for a whole batch on a DraftKings or FanDuel slate in about a tenth of a second. The solver I have always reached for is still in the tool, but as the referee rather than the player.
My free NHL lineup optimizer now builds lineups for Yahoo, the third site after DraftKings and FanDuel. I expected a Yahoo DFS NHL optimizer to be a matter of a new file parser and a new roster shape. It was mostly that, except for one line in Yahoo’s roster that broke three of my assumptions: two goalies. This post is about what had to change, which settings would have quietly made every lineup impossible, and the one new rule I added because of it: never repeat the same goalie pair.
An MIT NHL DFS paper found win probability was the only goalie predictor that mattered. So I rebuilt my NHL lineup optimizer around goalies.
Last week I came across a paper from three MIT operations research people — David Scott Hunter, Juan Pablo Vielma and Tauhid Zaman — called Picking Winners in Daily Fantasy Sports Using Integer Programming. It is about building a set of NHL DFS lineups with a solver, which is exactly what my free NHL lineup optimizer does, so I read it with a pencil in hand. They did not just run simulations: they entered real DraftKings contests and report that “we are able to rank in the top-ten multiple times in hockey and baseball contests with thousands of competing entries.” Then they donated the money — “around $15,000” — to the Greater Boston Food Bank, which I thought was a classy touch.
A good chunk of the paper is theorems and proofs about submodular functions. I skipped those. What I wanted was the strategy: what they stacked, what they found, and whether any of it should change my tool. One thing did, and it made the tool more than twice as fast.
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.
Continue reading “The Textbook Fix That Made My MILP Twice As Slow”
The free vehicle routing optimizer at routing.kindoflost.com used to think about a vehicle’s capacity as a single number. Fine for a lot of routes, but real fleets rarely run out of just one thing. A cargo van can be full on volume with plenty of weight capacity left, or maxed out on weight while the cargo area still has room, or simply out of pallet slots. I added a fix: the tool now supports three independent vehicle capacity constraints per route, plus a route time limit you can set per vehicle instead of one setting for the whole fleet.
