Hacker News new | past | comments | ask | show | jobs | submit login

Can you send me some of these results? I am pretty skeptical of such dramatic algorithmic improvements.

I don't think the point of an encyclopedia is to cover every single topic, as nice as that would be. If you're in the market for an encyclopedia, you are probably looking for a starting point, survey, or summary of stuff that's good to know. The algorithms you're thinking of are probably in very dry papers and monographs, accessible only to experts. If you were writing a commercial-grade generic MINLP solver, you would surely be looking at the latest papers for ideas, or you simply won't be competitive with existing solvers.




The paper I have mentioned can be found here https://arxiv.org/pdf/2206.09787

There are so many things that have only been invented in the last couple of years like RINS, MCF cuts, conflict analysis, symmetry detection, dynamic search,... (see e.g. Tobias Achterberg's line of work).

On the other hand, hardware improvements were not as relevant for LP and MILP solvers as one would expect: For instance, as of now there is still no solver that really uses GPU compute (though people are working on that). The reason is that parallelization of simplex solvers is quite though since the algorithm is inherently sequential (it's a descend over simplex vertices) and the actual linear algebra is very sparse (if not entirely matrix free). You can do some things like lookahead for better pricing or row/column generation approaches, but you have to be very careful in that (interior point methods are arguably nicer to parallelize but in many cases have a penalty in performance compared to simplex).

MILP/MINLP solvers are much nicer to parallelize at first glance since you can parallelize across branches in the branch-and-bound, but in practice that is also pretty hard: Moderns solvers are so efficient that it can easily happen that you spend a lot of compute exploring a branch that is quickly proven to be unncessary to explore by a different branch (e.g. SCIP, the fastest open-source MINLP solver is completely single threaded and still _somewhat_ competetive). This means that a lot of the algorithmic improvements are hidden inside the parallelization improvements. I.e. a lot of time has been spent on the question of "What do we have to do to parallelize the solver without just wasting the additional threads".


Thanks!




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: