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.
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.
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.
Obviously not everything will be easy to map into a classic optimization problem. And you may have a heuristic approach that is better for a problem. But the general solvers out there have gone a long long way.
Otherwise, the basic underlying algorithms are all the same, as in the textbook: branch-and-bound and so on.
whatever1•1d ago