Hacker News Reader

Comment by lqet | Hacker News Reader

> “In practice they are very efficient. They solve industrial-scale problems all the time,” sometimes with tens of thousands of variables.

Although the number of variables or constraints is not a good measure of the hardness of an ILP, "tens of thousands" is not that unusual. During my PhD, I often solved programs with millions of variables and constraints. These programs were so large that even "building" them in the solver library took several seconds. Impressively, gurobi was often able to optimize them in under 24 hours. I have two results here where gurobi solved 1M * 8M problems to optimality in under 2 hours. That was several years ago, so I expect newer versions to be even faster. Even for larger problems (around 5M * 50M) it often found provably near-optimal solutions (within 5% of optimality) very fast. gurobi is really an impressive piece of software, and free for academic use.

View on HN

I was on CPLEX team for a few years. Core developers are all PhDs from Stanford/MIT and etc. So it's very hardcore stuff, no less than AI research.

Completely agree that size is not a good proxy for estimating MIP difficulties. Internally we colllected a bunch of very hard problems to sovle from different domains. Some are actually pretty small, say a few thousand variables/constraints. IMHO what made hard problems difficult to solve is actually the 'intneral structure' of the problems. And modern industry solvers all have a lot of built-in heurstics to take advantages of the structures, i.e., what kind of cuts, presolve/diving/branching strategy to apply, how to get the bounds ASAP.

Interestinglly at some point some folks even tried using machine learning to predict strategies. Didn't work quite well back then (10+ years ago). There was some work of using seq2seq for MIP (pointer network, I think) a few years ago; worked OK. So I'm really looking forward to some breakthroughs by LLM.

It's a shame that after IBM aquired ILOG (which owns CPLEX), most of the ppl left for Gurobi.

> IMHO what made hard problems difficult to solve is actually the 'intneral structure' of the problems.

20 years ago I wrote a master’s thesis in computer vision. The stereo matching algorithm I developed could be expressed as a big integer linear program. But after pondering it for some time I realized it could also be expressed as a dynamic programming problem, with tiny integer linear programs as subproblems. Reduced the runtime by like a factor of 1000x, or more.

Not that uncommon.

I feel most of those big search problems could be solved much easier and quicker with some form of annealing/tree search/dynamic or greedy algorithms with results very close to the theoretical linear optimum

But of course those won't get you a thesis ;)

> with results very close to the theoretical linear optimum

In this case I could prove it was the globally optimal solution.

But this was only possible of course due to the internal structure of the problem: it was in effect a simpler problem hiding within a linear integer program. Standard solvers couldn’t find this structure, but it was possible to do by hand.

Reformulation is a good strategy for many hard problems.

It might also be possible to add problem-specific cuts/heurstics to the solver so that it can solve it fast.

Wow, this sounds interesting! Do you have a link to that thesis?

Unfortunately not. It’s on paper and in Swedish only.

Are you aware of any survey papers on some of the strategies used by (near) state of the art solvers?

Not the same person but maybe "Mixed-Integer Nonlinear Programming: A Survey of Algorithms and Applications" could be a good start? I haven't read it yet.

HiGHS is the best open source MILP solver at the moment, and MATLAB of all things has a pretty good explanation of how it works internally: https://nl.mathworks.com/help/optim/ug/mixed-integer-linear-...

I am an academic in the field. A good starting point would be Tobias Achterberg's PhD thesis:

"Constraint Integer Programming"

It details the implementation of SCIP, which is one of the leading open source solvers, and explains some of the most important tricks.

That said, there is a lot of literature out there; if you're interested in a particular aspect like e.g. presolving or cutting planes, then feel free to ask me further questions. It is worth noting that the implementation specifics are hidden by the top commercial solvers, so these are difficult to find anywhere

thank you very much!

when i investigated the situation five years ago in https://dercuano.github.io/notes/linear-optimization-landsca..., scip was not open source, though zimpl was. looking at https://github.com/scipopt/scip?tab=License-1-ov-file#readme, it appears that scip has become open-source since then, which is very welcome news!

how does highs compare to scip?

What's the situation with CPLEX these days? Is IBM still investing any serious resources into it? Gurobi keeps getting massively better (either in performance or expressiveness) every release.

As fare as I know it is jist a torso of its former glory. This is mostly the reason why we migrated to Gurobi.

CPlex has shown no progression in the benchmarks in the past years, so it is safe to assume that the number of developers they have employed is either 0 or maybe 1.

I love how researchers state that a piece of code doing actual work is "slow", once it takes a few seconds to run and yet windows 11 often takes multiple seconds to show me the context menu, when i right click something.

We need more optimization in this industry.

> We need more optimization in this industry.

The Windows 11 context menu lag (and overall Windows bloat) is a product of Conway's law. Microsoft creates bloated software because it's a monopoly. So, "optimization" in this case would essentially be antitrust action.

I think the other piece going into it is that hardware keeps getting faster. I would imagine especially so the hardware of the average Windows developer. If something doesn't generally appear to be slow to those building it, they're unlikely to spend a lot of time optimizing.

I'm a fan of including benchmarks in CI pipelines. The Windows developers should have a historical record [1] of the performance degradation and be forced to look at it daily.

[1]: https://x.com/jmmv/status/1671670996921896960

To be fair, that machine is pretty high-spec for NT 3.51, given that the minimum requirements are 12 MB RAM and a 386 (which tops out at 40 MHz). It'd certainly be nice to see that kind of performance in newer Windows versions, though.

> I think the other piece going into it is that hardware keeps getting faster.

It's also that you're expected to update windows whether or not they've actually improved performance. Why would microsoft prioritize that when the bulk of their sales are driven by other concerns, like enterprise sales and what some might call basic functionality (e.g. Windows Defender, when it was first released).

Hell, now they're moving to a service model and there's even less reason to court consumers directly.

Every other website is a mess of bloated and slow JavaScript code, both large and small sites alike.

I think the explanation isn't quite as simple as you make it seem.

it depends on what you're using it for. if you use an optimization algorithm after every keystroke to relayout the paragraph you're typing, it had better not take a few seconds to run. (and indeed there are optimization algorithms for that problem in particular that are much faster than a few seconds.)

Anyone have any idea how large Gosplan's* matrices were?

How about matrices used by RAF/AAF targeters for mincut purposes, eg https://en.wikipedia.org/wiki/Oil_campaign_of_World_War_II ?

* surprisingly, en.wikipedia has more information than ru.wikipedia, but neither even has a hint as to headcounts over the years, let alone more technical details.

I have the book “planning in the user” somewhere packed away. I remember it speaking about the number of variables and size of the problem in it. Sorry I don’t remember the numbers off the top of my head.

Obviously it didn’t work out though.

The other book worth getting is “red plenty”.

Planning in the U.S.S.R Problems of theory and Organisation

It is available on annas archive. Along with other similar books (Search: "Planning in the USSR").

LOOK UPON ME AND DESPAIR!

Interesting, do you mind telling a bit about the context where the problems you were solving arose? What was the application?

What kind of hardware did you need for such large problems? Single machine or cluster?

It was a graph drawing problem, solved on a single 16 core machine with around 64 GB of RAM.

Out of curiosity, how does one prove near optimality in problems like this?

E.g., do you assume that the optimal value is the one produced by the non-integer LP?

LPs can prove optimality of a result but sometimes this is to expensive and you stop as soon as you reach near optimality based on known bounds.

For several problems you can prove lower and/or upper bounds for the optimal results. For example you can prove that a route between two points may not be shorter than their distance.

If you use LP in production you often don't care about optimality and can work with suboptimal results very well. Worst case you stop after a timeout and just pick the best result.

Edit: I forgot to mention that during solving of a LP you usually get dynamically computed bounds. The branch and bounds algorithm works by computing bounds on relaxed problems that give upper bounds for the original problem.

It is called duality. For each linear program that is maximizing, you can find a dual linear program wich is minimization. They both have the same optimal objective value. Thus one serves as a lower bound and the other as an upper bound on the optimal objective value. The gap between them is used to measure the closeness to the global optima.

Great thing is that you can find the dual really easily and each feasible solution of the primal problem can be used to get a feasible solution of the dual.

The math behind that is really neat.

Reply on news.ycombinator.com