3 ms·

Speaking of optimization libraries, I've been checking out https://developers.google.com/optimization/ https://developers.google.com/optimization/ for schedulin

Speaking of optimization libraries, I've been checking out https://developers.google.com/optimization/ https://developers.google.com/optimization/ for scheduling and assignment problems. The documentation is not... wonderful, but it has a lot of examples and a decent Python API. I recently did an "Intro to OR" class and most of the tools we used were proprietary. I've been looking for more open source tools (and more info on OR in general, I think it's fascinating!). Edit: NLOpt (https://nlopt.readthedocs.io/en/latest/ https://nlopt.readthedocs.io/en/latest/) is also a nice suite of optimization algorithms for non-linear optimization.

wenc 9y ago
I highly recommend taking a look at the COIN-OR (Computational Infrastructure for Operations Research) project page. All the code is open-source. There are some amazing solvers in that list. https://www.coin-or.org/projects/ https://www.coin-or.org/projects/ The only issue is that much of the code on that site is very cutting-edge and academic. You may need to read a few benchmarks/publications to figure which solvers are production quality and which are not. That said, a handful of these free solvers are so well-written that they exceed the performance of many commercial solvers for certain types of optimization problems. (A notable exception is MIPs. Commercial MIP solvers like Gurobi or CPLEX are orders of magnitude better than the open-source CBC or GLPK. CBC is still pretty ok though, and I bundle it when I need to include a free solver in my code to solve smaller problems.)
- twic 9y ago
  I've used the linear programming bit of COIN-OR - Clp and Cbc. They may not be as good as the commercial solvers, but they're still way better than the other open-source options. That is particularly impressive given that, AIUI, they are largely the work of one man, John Forrest. For general optimisation, i've used NLopt. It was very easy to use, and has a pretty sensible set of algorithms. One thing i've learnt is that comparing optimisation algorithms is really hard. One might be better at one problem, one at another. One pretty general axis of variation is problem size: some algorithms scale to orders of magnitude more variables (or constraints etc) than others. In particular, i get the impression that a lot of the cutting-edge research is about being able to solve huge problems at all, or in hours instead of days. Perhaps those algorithms will be more useful for ML hyperparameter optimisation, but unfortunately, my needs are about solving much simpler problems in a fraction of a second. I get a lot more excited about Michael Powell's algorithms, which are cunning but simple, and work well on my problems.
  - xoroshiro 9y ago
    >One thing i've learnt is that comparing optimisation algorithms is really hard It still boggles my mind how simplex, something that theoretically runs worse that interior point methods is competitive (at least based on what I've read online). I guess with these problems, the instances of the problem has a huge effect on how long approaches take. >In particular, i get the impression that a lot of the cutting-edge research is about being able to solve huge problems at all This is also the impression I get. When I look at benchmarks (btw, does anyone know an updated publication for these? A lot of what I find seems to be from years ago. I'm not sure how fast development of these are, but it would be nice to be updated once in a while) it always has some measure of time along with number of instances solved. >Perhaps those algorithms will be more useful for ML hyperparameter optimisation I thought about this, and maybe the reason why they largely don't use these have to do with getting results that are good enough (generalize well). A global optimum might not be worth the effort, so they stick to some variant of gradient descent. The measure they look at, after all, is performance on the test set. Aside from that, there may be something specific about a well defined problem that they can use to speed computations up, and a more general approach probably can't assume these for other instances of NLP for example.
    - tavert 9y ago
      > does anyone know an updated publication for these? Hans Mittelmann (also a wonderful individual) has you covered: http://plato.la.asu.edu/bench.html http://plato.la.asu.edu/bench.html
    - wenc 9y ago
      > It still boggles my mind how simplex, something that theoretically runs worse that interior point methods is competitive (at least based on what I've read online). I guess with these problems, the instances of the problem has a huge effect on how long approaches take. Well, theoretical worst cases are just that. They are worst case bounds. People think NP-hard problem are intractable, but this is a misunderstanding. Many NP-hard problems can actually be solved with fairly good average case performance. Case in point: the Simplex method is worst-case exponential time, but its average case performance is actually pretty good. When Khachiyan first came up with his elipsoid method, it was polynomial time but in practice it was too slow. Karmarkar's interior point algorithm was polynomial time too, but performs much efficiently. These days though, solve times are predominantly affected by solver heuristics and randomness. The choice of Simplex vs Interior Point does not make a significant difference in many cases.

wenc 9y ago

I highly recommend taking a look at the COIN-OR (Computational Infrastructure for Operations Research) project page. All the code is open-source. There are some amazing solvers in that list. https://www.coin-or.org/projects/ https://www.coin-or.org/projects/ The only issue is that much of the code on that site is very cutting-edge and academic. You may need to read a few benchmarks/publications to figure which solvers are production quality and which are not. That said, a handful of these free solvers are so well-written that they exceed the performance of many commercial solvers for certain types of optimization problems. (A notable exception is MIPs. Commercial MIP solvers like Gurobi or CPLEX are orders of magnitude better than the open-source CBC or GLPK. CBC is still pretty ok though, and I bundle it when I need to include a free solver in my code to solve smaller problems.)

twic 9y ago
I've used the linear programming bit of COIN-OR - Clp and Cbc. They may not be as good as the commercial solvers, but they're still way better than the other open-source options. That is particularly impressive given that, AIUI, they are largely the work of one man, John Forrest. For general optimisation, i've used NLopt. It was very easy to use, and has a pretty sensible set of algorithms. One thing i've learnt is that comparing optimisation algorithms is really hard. One might be better at one problem, one at another. One pretty general axis of variation is problem size: some algorithms scale to orders of magnitude more variables (or constraints etc) than others. In particular, i get the impression that a lot of the cutting-edge research is about being able to solve huge problems at all, or in hours instead of days. Perhaps those algorithms will be more useful for ML hyperparameter optimisation, but unfortunately, my needs are about solving much simpler problems in a fraction of a second. I get a lot more excited about Michael Powell's algorithms, which are cunning but simple, and work well on my problems.
- xoroshiro 9y ago
  >One thing i've learnt is that comparing optimisation algorithms is really hard It still boggles my mind how simplex, something that theoretically runs worse that interior point methods is competitive (at least based on what I've read online). I guess with these problems, the instances of the problem has a huge effect on how long approaches take. >In particular, i get the impression that a lot of the cutting-edge research is about being able to solve huge problems at all This is also the impression I get. When I look at benchmarks (btw, does anyone know an updated publication for these? A lot of what I find seems to be from years ago. I'm not sure how fast development of these are, but it would be nice to be updated once in a while) it always has some measure of time along with number of instances solved. >Perhaps those algorithms will be more useful for ML hyperparameter optimisation I thought about this, and maybe the reason why they largely don't use these have to do with getting results that are good enough (generalize well). A global optimum might not be worth the effort, so they stick to some variant of gradient descent. The measure they look at, after all, is performance on the test set. Aside from that, there may be something specific about a well defined problem that they can use to speed computations up, and a more general approach probably can't assume these for other instances of NLP for example.
  - tavert 9y ago
    > does anyone know an updated publication for these? Hans Mittelmann (also a wonderful individual) has you covered: http://plato.la.asu.edu/bench.html http://plato.la.asu.edu/bench.html
  - wenc 9y ago
    > It still boggles my mind how simplex, something that theoretically runs worse that interior point methods is competitive (at least based on what I've read online). I guess with these problems, the instances of the problem has a huge effect on how long approaches take. Well, theoretical worst cases are just that. They are worst case bounds. People think NP-hard problem are intractable, but this is a misunderstanding. Many NP-hard problems can actually be solved with fairly good average case performance. Case in point: the Simplex method is worst-case exponential time, but its average case performance is actually pretty good. When Khachiyan first came up with his elipsoid method, it was polynomial time but in practice it was too slow. Karmarkar's interior point algorithm was polynomial time too, but performs much efficiently. These days though, solve times are predominantly affected by solver heuristics and randomness. The choice of Simplex vs Interior Point does not make a significant difference in many cases.