An Intro to Integer Programming for Engineers: Simplified Bus Scheduling
Integer programming often seems magical. I remember early grad school and seeing &quot;Optimal and Near-optimal Global Register Allocation Using 0–1 Integer Programming&quot; by Goodwin et al, where the very crunchy problem of register allocation was solved largely by punting it to a ILP solver. Gotchas abounded but it was eye opening to see how many hard problems could be solved (or at least adequately approximated) in this fashion.<p>I think this is one of those techniques that every serious computer scientist should have in their toolbox. Someone who knew some statistics, a smattering of something like SMT (enough to drive Z3) and some linear programming could routinely resemble Gandalf at any shop that has people struggling with difficult problems.<p>The main thing is not to turn into a cookbook guy. I&#x27;ve known a few people whose ability to just build an actual algorithm to solve some interesting problem has atrophied since they reach for a ILP solver the minute anything gets difficult.