Integer Programming (1977) [pdf] | Hacker News Reader

Integer Programming (1977) [pdf]

web.mit.edu

51 pointstodsacerdoti19 comments

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!

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.

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.

I know about only one such library, and works great for toy problems: PuLP [0][1].

[0]: https://coin-or.github.io/pulp/

[1]: https://pypi.org/project/PuLP/

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

Many use Z3 for type checking like F*, Liquid Haskell, Dafny.

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/

Ok, we'll put that year above instead. Thanks!

Reply on news.ycombinator.com