4 ms·

I'm one of the author of the post, happy to answer any question.

doubtfuluser 7y ago
Pretty cool work. Can you give any insights on the silver you used - especially the OSS ones. I had mixed (pun intended) experiences and would love to hear other opinions
- sanxiyn 7y ago
  Looking at the linked source, it uses CVXPY which can use many solvers. The default is set to GLPK.
ptah 7y ago
could this be opensourced and added to linux
- sanxiyn 7y ago
  It is already open source. I don't see why this belongs in Linux kernel though.
  - mochomocha 7y ago
    Right. Our approach is to move more logic into user-space so we can implement data/ML-driven solutions more easily.
ruuda 7y ago
I suppose the cost of running the prediction service is made up for by the improved workload performance. How do you make that trade off between the MIP solver budget and resources spent training the model on the one hand, and workload throughput gains or latency reductions on the other hand?
- mochomocha 7y ago
  Yes. In our case it's definitely worth it. Another interesting thing to consider is by moving from a kernel-level generic solution (Linux CFS) towards ML-driven systems that depend on the actual workloads we run on all of our clusters, it also implies different ways of debugging and iterating on software. We believe it's a net positive in our case.
yomritoyj 7y ago
In my experiments with MIP there was a dramatic performance difference between free and non-free solvers. Did you also experience this?
- 7thaccount 7y ago
  I'm not OP, but work with MIP solvers. Yes, there is a massive difference between the commercial (CPLEX, GUROBI, and maybe XPRESS) versus the best open source solvers (CBC/CLP and GLPK). My industry can only use the open source solvers for prototyping small models and could never use one for production with the size models we have. The commercial solvers are extremely expensive too.
- mochomocha 7y ago
  Definitely.
- wenc 7y ago
  I worked with MIPs for 8 years and commercial solvers have always been several orders of magnitude faster/better than open-source solvers. This is generally true for domain-specific software -- unlike general purpose software, incenting a small pool of specialized talent to make open-source contributions is always hard. The key to high performance in MIPs comes from having good heuristics, not necessarily from improving the basic algorithms (the algorithms are pretty standard -- simplex or interior point). Finding effective heuristics is hard and tedious, but they make a significant difference in solution speed. For instance, naive Simplex may take 40 minutes to solve a problem but with heuristics the solution time might be 5 seconds. That said, Cbc is competitive for smaller problems, and here's the thing: many production sized problems aren't that big -- it really depends on your problem domain. I've deployed commercial solvers on Cbc (30k variables/constraints) and it was more than adequate. I don't have any details on this, but Gurobi (a best of class solver) also offers an on-demand cloud SaaS which you can pay for on demand [1]. The economics of this may work out for some types of problems. [1] https://www.gurobi.com/pdfs/user-events/2017-frankfurt/Gurobi.pdf https://www.gurobi.com/pdfs/user-events/2017-frankfurt/Gurob... Also, if you're in academia, you can get Gurobi/CPLEX licenses for free (yes). My research group in grad school didn't spend a cent on these solvers, and we still got a taste of best-of-class solution performance (that's how they get you :).

Pretty cool work. Can you give any insights on the silver you used - especially the OSS ones. I had mixed (pun intended) experiences and would love to hear other opinions

sanxiyn 7y ago
Looking at the linked source, it uses CVXPY which can use many solvers. The default is set to GLPK.

ptah 7y ago

could this be opensourced and added to linux

sanxiyn 7y ago
It is already open source. I don't see why this belongs in Linux kernel though.
- mochomocha 7y ago
  Right. Our approach is to move more logic into user-space so we can implement data/ML-driven solutions more easily.

ruuda 7y ago

I suppose the cost of running the prediction service is made up for by the improved workload performance. How do you make that trade off between the MIP solver budget and resources spent training the model on the one hand, and workload throughput gains or latency reductions on the other hand?

mochomocha 7y ago
Yes. In our case it's definitely worth it. Another interesting thing to consider is by moving from a kernel-level generic solution (Linux CFS) towards ML-driven systems that depend on the actual workloads we run on all of our clusters, it also implies different ways of debugging and iterating on software. We believe it's a net positive in our case.

yomritoyj 7y ago

In my experiments with MIP there was a dramatic performance difference between free and non-free solvers. Did you also experience this?

7thaccount 7y ago
I'm not OP, but work with MIP solvers. Yes, there is a massive difference between the commercial (CPLEX, GUROBI, and maybe XPRESS) versus the best open source solvers (CBC/CLP and GLPK). My industry can only use the open source solvers for prototyping small models and could never use one for production with the size models we have. The commercial solvers are extremely expensive too.
mochomocha 7y ago
Definitely.
wenc 7y ago
I worked with MIPs for 8 years and commercial solvers have always been several orders of magnitude faster/better than open-source solvers. This is generally true for domain-specific software -- unlike general purpose software, incenting a small pool of specialized talent to make open-source contributions is always hard. The key to high performance in MIPs comes from having good heuristics, not necessarily from improving the basic algorithms (the algorithms are pretty standard -- simplex or interior point). Finding effective heuristics is hard and tedious, but they make a significant difference in solution speed. For instance, naive Simplex may take 40 minutes to solve a problem but with heuristics the solution time might be 5 seconds. That said, Cbc is competitive for smaller problems, and here's the thing: many production sized problems aren't that big -- it really depends on your problem domain. I've deployed commercial solvers on Cbc (30k variables/constraints) and it was more than adequate. I don't have any details on this, but Gurobi (a best of class solver) also offers an on-demand cloud SaaS which you can pay for on demand [1]. The economics of this may work out for some types of problems. [1] https://www.gurobi.com/pdfs/user-events/2017-frankfurt/Gurobi.pdf https://www.gurobi.com/pdfs/user-events/2017-frankfurt/Gurob... Also, if you're in academia, you can get Gurobi/CPLEX licenses for free (yes). My research group in grad school didn't spend a cent on these solvers, and we still got a taste of best-of-class solution performance (that's how they get you :).