Comment by hustwindmaple1 | Hacker News Reader

Comment by hustwindmaple1 | Hacker News Reader

Parent Full thread

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.

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.

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?

Reply on news.ycombinator.com