If Google can "basically determine web standards", then I don't see how it's possible for anyone else to "still have a seat on the table". I mean, if they cared enough about it and were actually on the table in the first place...
>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.
> 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.
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.
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.
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:
JuMP and Pyomo are both exactly that. Pyomo is as near as you can get to an AMPL clone with python syntax. JuMP is an optimization DSL using Julia macros.
Maybe I was confusing my terms or something. I think of these as like an API as well, although packaged into a nice library that automates some stuff. So I guess I'll try to describe my ideal scenario instead.
What I was thinking of was a common language that can be used by all solvers. Similar to how C can be compiled by gcc or clang, this language can be used directly with the solver binary. Something like `export CC=my_solver` and `CC -d data.dat -m model.mod`, if you will.
What a lot of these projects do feels like calling a solver by translating it into some format that's different for everyone, whereas I wanted for the solvers to all agree on some language.
Or at the very least, some standard similar to how languages have libraries for something like XML. It would be nice if JuMP and PyOmO could read these standardized formats.
Then again, it's probably a pain to implement and even C compilers implement different extensions. But one can dream.
See the COIN-OR Optimization Services (OS) project for a solver-independent xml format called OSiL. It's functionally equivalent to AMPL .nl format but more human-readable. Unfortunately the osil readers for solvers have more performance problems and bugs than .nl readers, since the AMPL format has been around longer and is commercially supported.
The proprietary part of AMPL is the program that turns human-readable .mod and .dat files into low-level .nl encodings of the problem representation. The .nl format is documented, and there's an MIT licensed library on netlib (and now github too) that reads it and evaluates functions, constraints, gradients, Jacobians, Hessians, etc. (AD is super useful and has been around way longer than the deep learning popularization of it.)
Julia has a low-level solver-independent API called MathProgBase that sits between solver wrappers and modeling languages like JuMP / Convex.jl. It's in the process of being rewritten as MathOptInterface, but it would allow people to write solvers in pure Julia and be usable right away with JuMP.
> whereas I wanted for the solvers to all agree on some language.
Umm, they (mostly) do. Pyomo supports the AMPL .nl format, which means you can call any AMPL solver from Pyomo (most COIN-OR solvers have AMPL interfaces). The AMPL .nl format is the de facto standard for open-source optimization solvers because it's the only open standard, I believe [0].
So you would define your mathematical program in Pyomo (which isn't a terribly challenging syntax compared to AMPL). When you invoke solve, Pyomo will spit out an .nl file and call a solver (which reads the .nl file, solves the problem, and outputs a .sol file which can be read back into Pyomo).
Incidentally this is exactly how it works in AMPL as well -- all the interop is done through .nl and .sol files. I recommend reading [0] to understand how this works.
Oh, wow. I couldn't really figure out which parts of AMPL were proprietary and I guess I immediately dismissed it after that without understanding how it worked.
As for Pyomo, while at first glance I dislike the syntax (it's not as easy to share with others, at least compared to something like GNU MathProg, where the receiver doesn't need to concern themselves with python or julia), I like python enough to maybe give it a try. I'll have to learn more about it though. Thanks to you and the others!
I guess it doesn't matter that much, but if there were a common language, it would be a nice feature that would allow you to skip the middleman altogether and have simpler dependencies if you know which solvers you want.
It's the common language that matter more though. I've used GAMS in my undergrad, so I'm under the impression that it's had at least some adoption, but it's proprietary AFAIK. I've know some people who use AMPL too, which also seems popular, but I'm not sure about it's licenses.
You might also be interested in looking at MiniZinc (http://minizinc.org/). It is mostly used int the constraint programming community, but the language is solver technology neutral and there are back-ends that translate to MIP systems.
Personally I enjoy using MiniZinc as a language for prototyping models in, and enabling me to experiment and compare various different solver technologies easily.
Probably the wrong engine to test this with then. Although it's interesting nonetheless. It's pretty well known that chess engines have this trade-off between searching and evaluating. Among the consistent top 3 I suppose Stockfish is the easiest to test, being open source and all. It's pretty well regarded that Komodo has the best evaluation function though. Even if it doesn't keep up with the nodes/sec of Houdini and Stockfish, it's consistently up there with the top 3. The other chess engines doen't even come close. (Fire is probably number 4 but is on a league of it's own. Not quite good enough to challenge the top 3, but eats everything else.)
I know it's complicated, between the hardware differences, search method used, etc. But when claiming that NNs beat hand crafted evaluation functions, keep in mind that Stockfish is probably are not the best choice to compare, since it has made different tradeoff choices to get more depth (which goes back to search method and hardware choices).
Thanks for that. My undergrad was Industrial Engineering but I always loved the Operations Research stuff (which I'm hoping will lead me to more CS-y stuff if I can get a job or a Masters or something). All that OR with LPs and MIPs was a headache and but somehow Stochastic programming, GAs and NNs were scary and I never even tried to understand them. I always thought people describing them as simple were probably geniuses or something. Maybe one day I'll understand the second half of that link.
For something as well known as shortest path, no. One thing about LP/MIP formulations though, is that it's arguably easier to extend. Not to say there aren't tricks to modifying existing algorithms, but most of the time, there is no need to spend all that time, when adding in a few variables or constraints will do the trick for this one problem that you will probably not need to revisit for quite a while.
I have some idea how it MIGHT work, but it would be a very boring solution involving 'learning' Stockfish's parameters and HOPING to find improvements to something like integrating time management and search/pruning into it.
I wouldn't bet on it though. SMP is notoriously hard to work with alpha-beta search and there are a lot of clever tricks (which is probably still not perfect). Maybe with ASICs, you could make it stronger, but then it wouldn't be as fair a comparison.
Well, all top engines did some kind of search on parameters, not sure if you can find much improvement there.
I'm talking about something similar to the described in the paper, 100% self-learned solution without using human heuristics, based on NNs. That could bring a totally new ideas into chess.
