6 ms·
Google Optimization Tools
- philip1209 11y agoIf you're interested in optimization with these same back-end solvers, check out the JuliaOpt tools from MIT. http://www.juliaopt.org/ http://www.juliaopt.org/
- peterwaller 11y agoIf there are any Googlers reading this, the first link takes you to google code, but the source has moved to GitHub.
- cornstalks 11y agoFixed! Though you might have a cached copy in your browser.
- bhilburn 11y agoThe docs and interface look great, and it's nice that each one comes with a sort of mini-walkthrough. If any Google devs read this, I do have one request: it would be awesome to see runtime analysis based on the theory / design of the provided code, with perhaps some explanation of why certain design decisions were made in the solution. It's already an excellent educational tool, and this seems like an easy way to make it even better.
- rurban 11y agoOld discussion of glop: https://news.ycombinator.com/item?id=8393200 https://news.ycombinator.com/item?id=8393200 (with python demo)
- chuckcode 11y agoAnybody familiar with this know if it has a good implementation of Levenberg–Marquardt algorithm? Or know of one somewhere else? I can't find anything in their docs about non-linear function solving which seems like something google must do a lot of.
- ovis 11y agoLooks like this is more LP oriented. There are numerous free implementations listed here: https://en.wikipedia.org/wiki/Levenberg%E2%80%93Marquardt_algorithm#Implementations https://en.wikipedia.org/wiki/Levenberg%E2%80%93Marquardt_al... Was there something special you needed?
- chuckcode 11y agoIdeally something c/c++ and liberal license. I'll take a look at ceres-solver to see how it works. Like that it is using Eigen under the hood to get benefit of SSE instructions.
- argomez 11y agohttp://ceres-solver.org/ http://ceres-solver.org/
- kxyvr 11y agoIs there a reason why you're looking for Levenberg-Marquardt over a trust-region Newton solver? In general, properly preconditioned matrix-free trust-region Newton solvers will give superior performance to Levenberg-Marquardt. Something like Optizelle http://www.optimojoe.com/products/optizelle http://www.optimojoe.com/products/optizelle can do that and is BSD licensed.
- chuckcode 11y agoThanks! That looks very interesting, will definitely try it out!
- hartator 11y ago> If you just want to play Sudoku, fire up Google Sheets and install our Sudoku add-on. Translated: Hey guys! We might do something that might get shutdown next year but we are still cool!
- sogen 11y agoLogged in just to upvote (y)
- shockzzz 11y agoKinda confused what this helps me do. Can someone explain?
- bitL 11y agoIt's for operations research stuff (like logistics, scheduling etc.), not software optimization.
- fridek 11y agoBasically it solves NP-complete problems that are solvable because of small set size and some clever constant optimizations. There are industries where it's a useful thing for scheduling, for example. Or you may want to solve travelling salesman when planning a trip.
- shoo 11y agoSome real-world examples with a little more flavour: * designing utility networks (e.g. energy / telecommunications) to be cheap / robust * routing vehicles / ships / parcels to serve all customers cheaply * dispatching and arranging emergency services vehicles (e.g. ambulances) to best cover anticipated future demand * managing inventory levels in blood banks. it goes off after a while! there are different types, some are substitutable. which types are better to keep in stock? * figuring out the most profitable way to chop animals into different cuts of meat
- santaclaus 11y agoLots of crazy image processing and computational photography techniques use linear programming and variants on all of these graph algorithms.
- imh 11y agoNumerical optimization of discrete/combinatorial problems.
- zxcvcxz 11y agoThe most surprising thing to me is how fast the page was able to load. Not really much faster than any regular web page, but a lot faster than most google pages with the material design. When they first started rolling out the new designs/code on google drive and trends I was lucky if the page even loaded. I'm impressed.
- habosa 11y agoThat's the new skin on developers.google.com, glad you like it! I think you'll find the whole thing is pretty snappy, it's rendered 99% on the server side besides a few presentational JS pieces.
- fridek 11y agoCoursera has a great course on discrete optimization [1] where I have learned and used or-tools. They are rather nice, but the documentation is half done (basically code is the best documentation) and some interfaces are not compatible with others. I ended up forking or-tools for my own use and tweaking many unexposed internals. I guess it's extremely difficult to implement generic optimization solver, so I won't complain, but be prepared it's not out-of-the-box thing (I doubt there is any). [1] https://www.coursera.org/course/optimization https://www.coursera.org/course/optimization
- mandeepj 11y agoThis course looks amazing. Thanks for sharing it
- graycat 11y ago> the documentation is half done The literature and documentation in operations research optimization is enormous, going back to the 1950s. The best of that literature is quite well written. For combinatorial optimization, there is George L. Nemhauser and Laurence A. Wolsey, 'Integer and Combinatorial Optimization', ISBN 0-471-35943-2, John Wiley & Sons, Inc., New York, 1999. The details of optimization are not always trivial, and several fairly challenging graduate applied math courses, complete with non-trivial theorems and proofs, can be needed for much depth in the subject. I've had four such courses and taught one. > I guess it's extremely difficult to implement generic optimization solver, A "solver"? Would be nice to have a "solver". Lots of people talk about giving a problem to a "solver". For linear programming, maybe usually can do that. Otherwise my experience is that asking for a general purpose solver is, for now, hopeless. Instead, for the real problems I've had success with, have to look carefully at the problem and exploit special structure particular to that problem. Typically part of the work involves doing some derivations using the math of optimization.
- matchu 11y agoI think we're talking about documenting the interface that or-tools provides. Even someone with an excellent understanding of the underlying concepts still needs to know exactly how or-tools exposes those concepts.
- bitL 11y agoNice! Just a question - are there distributed versions of these somewhere as well?
- swanson 11y agoWhile the documentation is a bit sparse (on the web, there are better docs buried in the source code), I found this library to be much easier to work with then the alternatives - which are mostly from academia and have a heavy emphasis on matrix operations. There are still some rough edges, but I was able to get the Python bindings installed and used it to write an optimizer for fantasy basketball[1]. I think the domain of solving problems by defining the constraints is super interesting. In my fantasy basketball example, I define the constraints for a valid roster (simple), then define how to score a roster, and less than a second later, I've got the optimal picks. One other neat feature of this library is that you can use it directly from Google Sheets - you can read inputs from your spreadsheets, run the optimizer code (javascript) on Google's boxes, and then write output back to your spreadsheet. [1]: https://github.com/swanson/degenerate https://github.com/swanson/degenerate
- jlhonora 11y agoAre there plans for Go bindings anytime soon?
- saosebastiao 11y agoJust wanted to mention that the or-tools constraint solver is absolutely top notch. It has been winning top3 places in the minizinc competition ever since it entered a few years ago, and placed first in 3 out of 4 categories last year. I've used it quite a bit, and with a few exceptions I've found its completeness relative to the Global Constraint Catalog to be excellent, especially so for open source software. Now if only they had a functional 3 dimensional Geost constraint :)
- tunnuz 11y agoI can also recommend the excellent Gecode (www.Gecode.org). Great documentation (basically a CP book), well designed, and maintained.
- xudafeng 11y agoMy source are all on GitHub.
- shoo 11y agoYou may be interested in a previous discussion of Optimisation / Operations Research in the context of FedEx. graycat's comments were particularly interesting: https://news.ycombinator.com/item?id=9281466 https://news.ycombinator.com/item?id=9281466
- amelius 11y agoCan these tools be run in the web-browser as well?