Encyclopedia of Optimization(link.springer.com) |
Encyclopedia of Optimization(link.springer.com) |
The danger of indexing too much on a canon of knowledge in a fast evolving field is that you're narrowing your view to a set of techniques that don't work so well on modern problems.
Deep learning for instance is a nonconvex optimization problem where we have a lot of practical knowledge on how to make it work well, but the theoretical knowledge of why it works so well is still being developed. This is a case where practice precedes theory.
Instead of an encyclopedia, I recommend subscribing to a (free) mailing list of pre-prints, Optimization Online.
Can anyone recommend a good didactic book or online course for a computer scientist with a good grasp of math and machine learning? It has to reach beyond linear problems.
Wtaf.
Unfortunately the thing is from 2008 and I suppose this kind of book doesn't age well.
[1] http://titan.princeton.edu/2010-10-11/EoO2/Encyclopedia_Opti...
> CCXXXI, 4622
Taf.
Projects like this are built on the work of academics, the majority of whom are publicly funded. By and large they resent the for-profit publishers who benefit from their work and sometimes reduce them to needing to pirate their own work.
People have tested old year 2000 lp and milp solvers against recent ones while correcting for hardware. Hardware improvements made up ~20x improvement, while lp solvers in general sped up 180x. MILP solvers speed up a full 1000x (Progress in mathematical programming solvers from 2001 to 2020).
Solvers from 2008 are entirely different levels of performance: there are many problems that are unsolvable by those that are solved to zero duality gap in less than a second by more modern solvers.
In MINLPs the difference is even more standing. This doesn't mean that those books are useless (they are quite good), but do not expect a solver based on those techniques to even play in the same league as modern solvers.
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.
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".