Integer Programming (1977) [pdf]

Posted4 months agoActive4 months ago

todsacerdoti

51 points

19 comments

web.mit.eduTechstory

calmpositive

Debate

20/100

Integer ProgrammingOptimizationOperations Research

Key topics

Integer Programming

Optimization

Operations Research

A 1977 PDF on Integer Programming is shared, sparking discussion on its applications, relevance, and state-of-the-art solvers in the field.

Snapshot generated from the HN discussion

Discussion Activity

Moderate engagement

First comment

Peak period

84-96h

Avg / period

Comment distribution15 data points

Loading chart...

Based on 15 loaded comments

Key moments

01Story posted
Sep 4, 2025 at 3:13 PM EDT
4 months ago
Step 01
02First comment
Sep 8, 2025 at 11:04 AM EDT
4d after posting
Step 02
03Peak activity
8 comments in 84-96h
Hottest window of the conversation
Step 03
04Latest activity
Sep 9, 2025 at 3:56 AM EDT
4 months ago
Step 04

Generating AI Summary...

Analyzing up to 500 comments to identify key contributors and discussion patterns

Discussion (19 comments)

Showing 15 comments of 19

nimih

4 months ago

1 reply

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

dang

4 months ago

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

abhishekbasu

4 months ago

2 replies

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.

taeric

4 months ago

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.

CuriouslyC

4 months ago

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.

dgan

4 months ago

1 reply

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

ngruhn

4 months ago

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

eachro

4 months ago

2 replies

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.

mmaaz

4 months ago

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.

__rito__

4 months ago

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/

timonoko

4 months ago

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.

mxkopy

4 months ago

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

pedrosbmartins

4 months ago

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!

gcy

4 months ago

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

whatever1

4 months ago

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

4 more comments available on Hacker News

View full discussion on Hacker News

ID: 45131091Type: storyLast synced: 11/20/2025, 4:29:25 PM

Want the full context?