Hacker News Reader

Comment by almostgotcaught | Hacker News Reader

> Theoretically if you derive tight enough cuts for the problem and the solution lies on a vertex of the relaxed simplex you you can get the optimal solution in polynomial time.

I hate when people cloak very obvious things in jargon to make those things seem more insightful and disguise how obvious they are. What you're basically saying is if you're lucky and you win the lottery then you'll be rich.

Ie yes we all know that if you luck out then interior point will give you the optimum in polynomial time. But the whole reason why MIP is np-hard is exactly because deriving those cuts in general isn't possible (at least currently).

> This is not what math programming does

So what gurobi/cplex/etc actually do is first try a bazillion symmetry transformations/warm start heuristics/etc but then ultimately it does boil down to search.

View on HN

No and No.

This way of thinking describes the plateau that MIP solvers hit in the 90's.

Then in 2000's they starting implementing actual math (valid cuts in the root node mainly, but also during the search), which what gave us the exponential speed ups we enjoy today.

So you would be right 30 years ago. You are wrong in 2024.

> No and No.

> which what gave us the exponential speed ups we enjoy today

You're just patently wrong because

1. P=?NP is still open

2. You can consult the implementation of any solver

There's really nothing more to be said about it because both of these bullets are formal proofs that you are wrong.

Simplex algorithm should never work given its exponential worst case performance. Yet it solves the vast majority of LP problems, including ones with billions of variables. It is the default algorithm for every solver despite the fact that we have a polynomial interior point method in our disposal. Go figure.

Worst case performance or NP completeness is not a predictor of how fast we can solve an optimization problem.

> should never work given its exponential worst case performance

This is again not true. We know why it works well. See the paper

"Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time"

by Spielmann and Teng.

We started understanding of why it works so well like 30 years after its first implementation (in the 1950's)? The paper you mention is written in the 2000s while the Simplex dominated the field from at least the 70's.

Meanwhile the GP would have discarded the simplex algorithm due to its worst case performance.

> Simplex algorithm should never work given its exponential worst case performance.

Note that it has been proven however that if you slightly perturbate the inputs then the expected complexity becomes polynomial, meaning the inputs for which it's exponential are actually just pathological cases and it is polynomial in practice.

Man, there was a lot of obtuse argument to wade through to get to this post. This is an interesting fact. Apparently this is the source?

https://arxiv.org/abs/cs/0111050

Honestly, the parent is pretty accurate. No one is claiming that P = NP. However, the technology to solved mixed integer programs has improved dramatically over the last 30 years and that improvement in performance has outpaced computational speed by multiple orders of magnitude. It's the algorithms.

I just went to pull up some numbers. The following comes from a talk that Bob Bixby gave at ISMP in 2012. He is the original author of CPLEX and one of the current owners of Gurobi. Between 1991 and 2007, CPLEX achieved a 29530x speedup in their solvers. Their 1997/98 breakthrough year attributes the following speedups, Cutting planes: 33.3x, presolve: 7.7x, variable selection: 2.7x, node presolve 1.3x, heuristics: 1.1x, dive probing 1.1x. I don't have a paper reference for these numbers and I don't think he has published them, but I was at the talk.

The point is that integer programming solvers perform unreasonably well. There is theory as to why. Yes, there is still a lot of searching. However, search in-and-of-itself is not sufficient to solve the problems that we regularly solve now. Further, that increase in performance is not just heuristics.

Here is the paper

https://www.emis.de/journals/DMJDMV/vol-ismp/25_bixby-robert...

FYI we’ve probably crossed paths :)

Laugh. Probably! I gave a talk at that conference titled, "Software Abstractions for Matrix-Free PDE Optimization with Cone Constraints." I still work in the field, so you want to talk algorithms sometime, feel free to send me an email. I keep my email off of HN to limit spam, but if you search for the lead author on that presentation, it should list my website.

Reply on news.ycombinator.com