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.
Oh yeah, there are whole subfields of engineering that the current crop of AI deep learning engineers are mostly unfamiliar with. I've been able to find places where I can make significant advances on the state of the art in AI through incorporation of concepts from decision theory, control theory, process engineering, constraint optimization, etc.
The amusing ones, to me, are the people that know of the techniques, but are convinced they can't apply.
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.
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!
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.
The state of the art solvers are the proprietary ones like Gurobi, FICO, Cplex, Mosek, etc. A major contributor to the proprietary "sauce" is in the heuristics they use. For example, all solvers will have a "presolve" phase which attempts to eliminate redundant constraints/variables. There may be some ML they are using behind the scenes to derive these heuristics, I'm not sure, although I know it is a major research area.
Otherwise, the basic underlying algorithms are all the same, as in the textbook: branch-and-bound and so on.
Do modern compiler (register allocation/ instruction generation) involve some kind of integer programming or constraint solving? I vaguely remember compilers using Z3 solver
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.
I find the idea of a language model solving an integer programming problem odd. LLMs can barely do basic arithmetic. How do you imagine this happening?
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.