Integer programming is one of those things every CS undergrad hears about, then spends a career quietly rediscovering in different guises. In practice, integer constraints are where your “cute model” goes to die.

Branch-and-bound, cutting planes, implicit enumeration… they’re all ways of admitting “brute force, but try to be clever about it.”

That said, the irony is half the problems that matter in the real world, like capital budgeting, scheduling, routing, warehouse placement, are integer problems.

LP relaxations are nice, but you can’t run an airline with fractional pilots or build 2.3 hospitals. So you either lean on heuristics, or you call CPLEX/Gurobi and pray.

The fact that modern solvers still do as well as they do is, honestly, one of the underappreciated miracles of applied cs.

I've always had the impression that Mathematical programming esp. Mixed integer programming/Integer programming is largely "unknown" outside of core engineering and operations research. It's an excellent framework to solve a whole host of problems that arise in business and elsewhere, which are solved using suboptimal (hah) heuristics instead.

Okay, maybe I was a bit harsh, but it definitely doesn't pop up as often as deep learning and statistical machine learning. For those who wish to get deeper into this, I highly recommend Optimization over Integers by Bertsimas and Weismantel.

First time I came across integer programming (and mathematical programming generally) was when studying hydroelectric power generation planning, for a masters I ended up not pursuing. Then, when selecting a masters in CS, I ended up working with an advisor who used mixed-integer programming applied to classic machine learning models (mainly optimal decision trees). A fascinating and widely applicable method, indeed!

Or how to solve your 2^n problem in polynomial time (most of the times)

One thing I discovered on 8080 was that 0FFFFH is "infinity". Meaning it is better to produce this infinity than zero-division error, when system is oscillating around zero. Otherwise you have to insert zero-tests everywhere and waste precious clock cycles.

Does anyone know what the state of the art industry solvers do for these problems? I had dabbled a bit in ml approaches to combinatorial optimization with great interest a few years back, but I don't think any of these rl based methods ended up being used in production.

There is a textbook for this in case you don't know. https://link.springer.com/book/10.1007/978-3-319-11008-0

Do modern compiler (register allocation/ instruction generation) involve some kind of integer programming or constraint solving? I vaguely remember compilers using Z3 solver

Nice, my undergrad thesis used this stuff. I truly believe if P=NP the proof will be an mILP solving HC or similar

The copyright on this text seems to be 1977, not 2002. See: https://web.mit.edu/15.053/www/