5 ms·

There's a whole class of deterministic Global Optimization solvers on COIN-OR [0] that don't seem to get noticed outside the Operations Research/Applied math co

by wenc 9y ago

There's a whole class of deterministic Global Optimization solvers on COIN-OR [0] that don't seem to get noticed outside the Operations Research/Applied math community. (many are free and open source, e.g. Couenne) These solvers (BARON [1], ANTIGONE [2], Couenne [3] etc.) are capable of solving nonconvex global optimization problems that are structurally more complicated (i.e. non-ML applications) than the ones presented in the article linked above. They employ a bunch of mathematically-rigorous methods such as interval analysis, branch-and-cut and McCormick relaxations. There's a treasure trove of little ideas from decades of global optimization research that I feel the Deep Learning community could benefit from taking a peek at. [0] https://neos-server.org/neos/solvers/index.html https://neos-server.org/neos/solvers/index.html [1] http://archimedes.cheme.cmu.edu/?q=baron http://archimedes.cheme.cmu.edu/?q=baron [2] http://helios.princeton.edu/ANTIGONE/index.html http://helios.princeton.edu/ANTIGONE/index.html [3] https://www.coin-or.org/Couenne/ https://www.coin-or.org/Couenne/

blt 9y ago
Thanks for sharing this!
perturbation 9y ago
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.
rsp1984 9y ago
Absolutely. Adding to the list, SIMPLE [1] was recently trending on HN [2]. It looks very applicable to hyperparameter optimization. [1] https://github.com/chrisstroemel/Simple https://github.com/chrisstroemel/Simple [2] https://news.ycombinator.com/item?id=16241659 https://news.ycombinator.com/item?id=16241659
xoroshiro 9y ago
Glad to see someone posted about COIR-OR! I've been looking at open source solvers for a while now to solve an MIP, and this one seems to be the best. There is this annoying thing about the whole ecosystem though, aside from the proprietary bits. I started by looking at GLPK and wrote my MIP in GMPL. For some reason a lot of tools I looked at don't "just work". I have to export it to some other format. It works, but feels like a work-around. I wish there were a lingua franca in this domain and sort of have support from all major solver implementations, but each one seems to have their own way, or just provide an API (ehem google/or-tools) I am happy I can make it work, but it may not be as easy for others.
- tavert 9y ago
  > I wish there were a lingua franca in this domain and sort of have support from all major solver implementations JuMP is kind of that in terms of modeling software - http://www.juliaopt.org/ http://www.juliaopt.org/ Pyomo is also pretty useful if you'd rather use Python than Julia, though it's not as well-documented and doesn't make installation of the open-source solvers quite as easy for you.
  - xoroshiro 9y ago
    Thanks, but it was not really what I was looking for. I was looking for something that feels closer to a DSL than an API. In OR, a language like AMPL (IIRC, by Brian Kernighan) or GAMS is typically used where you define sets, variables, etc. It's something I feel I can more easily share to co-workers with different backgrounds, since it's closer to math, and follows the whole objective function, constraint, etc. organization in OR problems. If you want to get a feel for it, here's an example in GMPL, which is a subset of AMPL used in GLPK: https://en.wikibooks.org/wiki/GLPK/GMPL_%28MathProg%29 https://en.wikibooks.org/wiki/GLPK/GMPL_%28MathProg%29
    - deleted 9y ago
      [deleted]
    - tavert 9y ago

by wenc 9y ago

blt 9y ago

Thanks for sharing this!

perturbation 9y ago

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.

rsp1984 9y ago

Absolutely. Adding to the list, SIMPLE [1] was recently trending on HN [2]. It looks very applicable to hyperparameter optimization. [1] https://github.com/chrisstroemel/Simple https://github.com/chrisstroemel/Simple [2] https://news.ycombinator.com/item?id=16241659 https://news.ycombinator.com/item?id=16241659

xoroshiro 9y ago

Glad to see someone posted about COIR-OR! I've been looking at open source solvers for a while now to solve an MIP, and this one seems to be the best. There is this annoying thing about the whole ecosystem though, aside from the proprietary bits. I started by looking at GLPK and wrote my MIP in GMPL. For some reason a lot of tools I looked at don't "just work". I have to export it to some other format. It works, but feels like a work-around. I wish there were a lingua franca in this domain and sort of have support from all major solver implementations, but each one seems to have their own way, or just provide an API (ehem google/or-tools) I am happy I can make it work, but it may not be as easy for others.

tavert 9y ago
> I wish there were a lingua franca in this domain and sort of have support from all major solver implementations JuMP is kind of that in terms of modeling software - http://www.juliaopt.org/ http://www.juliaopt.org/ Pyomo is also pretty useful if you'd rather use Python than Julia, though it's not as well-documented and doesn't make installation of the open-source solvers quite as easy for you.
- xoroshiro 9y ago
  Thanks, but it was not really what I was looking for. I was looking for something that feels closer to a DSL than an API. In OR, a language like AMPL (IIRC, by Brian Kernighan) or GAMS is typically used where you define sets, variables, etc. It's something I feel I can more easily share to co-workers with different backgrounds, since it's closer to math, and follows the whole objective function, constraint, etc. organization in OR problems. If you want to get a feel for it, here's an example in GMPL, which is a subset of AMPL used in GLPK: https://en.wikibooks.org/wiki/GLPK/GMPL_%28MathProg%29 https://en.wikibooks.org/wiki/GLPK/GMPL_%28MathProg%29
  - deleted 9y ago
    [deleted]
  - tavert 9y ago