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.

The most useful feature in math programming is the optimality bound estimate it offers.

It is very important to know that every single time your solution is at worst 1% away from the proven optimal one. If it is not, you get a signal and you can invoke mitigations.

This is when pure heuristics fail. They may work 99% of the time giving you near optimal solutions, but that 1% they will fail you and even worse, you will have no idea that they failed you.

Approximation algorithms also offer some bounds, but typically they are very loose, to the point that they are not useful to the bean counters. Nobody is running their fleet using (exclusively) the Christofides algorithm.

There are some new research that applies transformers to MIPs. I'm looking forward to LLMs cracking MIPs at some point and beat those commercial solvers.