Optimization solvers: missing link for fully open-source energy system modeling • Hacker News Board

Re: Optimization solvers: missing link for fully open-source energy system modeling

#21

Post by quanto » Sun, May 01, 2022, 2:31 AM UTC

SparseRunner wrote: post #17

quanto wrote: post #7

>even the current interior point implementation in HiGHS can be unacceptably slow relative to Gurobi (60-100 times slower). Considering that even Gurobi requires a couple of days to solve huge practical problems illustrates that the use of current open source solvers is totally impractical. The aim of this proposal is to identify key solver enhancements in the short, medium and long term that will help to bridge the…

Thanks. Matching Gurobi is not feasible, but HiGHS wants those who depend on open-source solvers to be able to work with bigger models than is currently possible. Once HiGHS has a good interior point solver (for QP) - the main aim of this proposal - the vision is to develop a nonlinear programming solver.

In your expert opinion, what is Gurobi's edge? The foundational mathematical formulation for solvers has been known for decades. I have read that Gurobi has many heuristics that statistically work well against real world problems.

What are concrete technical challenges HiGHS needs to solve to bridge the gap with Gurobi?

(my academic background is in numerical analysis/scientific computing but I didn't specialize in writing optimizers)

Re: Optimization solvers: missing link for fully open-source energy system modeling

#22

Post by SparseRunner » Sun, May 01, 2022, 7:23 AM UTC

quanto wrote: post #21

SparseRunner wrote: post #17

Earlier quoted context omitted.

Thanks. Matching Gurobi is not feasible, but HiGHS wants those who depend on open-source solvers to be able to work with bigger models than is currently possible. Once HiGHS has a good interior point solver (for QP) - the main aim of this proposal - the vision is to develop a nonlinear programming solver.

In your expert opinion, what is Gurobi's edge? The foundational mathematical formulation for solvers has been known for decades. I have read that Gurobi has many heuristics that statistically work well against real world problems. What are concrete technical challenges HiGHS needs to solve to bridge the gap with Gurobi? (my academic background is in numerical analysis/scientific computing but I didn't specialize in w…

For interior point the key is writing a multicore matrix decomposition code that exploits sparsity and the range of problem structure that is encountered. For MIP it's having techniques to exploit the many different problem features that occur and ensuring that they are used intelligently.

Re: Optimization solvers: missing link for fully open-source energy system modeling

#23

Post by SparseRunner » Sun, May 01, 2022, 8:42 AM UTC

rwlincoln wrote: post #5

I am surprised not to see any mention of the OSQP (Operator Splitting Quadratic Program) solver. It is the most impressive open source solver of this type that I have seen published in recent years. It appears to have been developed as a collaboration between Princeton, ETH Zurich, Oxford, Stanford and some other prestigious names. The benchmarks show that it compares favorably with leading proprietary solvers: https…

OSQP is fast, but is only for QP, not LP.

The "benchmarks" (https://github.com/osqp/osqp_benchmarks) include some important problem classes but are random so, for general QP, are not valid. On the industry standard benchmarks (http://plato.asu.edu/ftp/qpbench.html) OSQP doesn't look so good, and it's not even tested against commercial solvers (http://plato.asu.edu/ftp/cconvex.html).

Our experience with it on general benchmarking problems is that it can struggle to get sufficiently accurate dual values to the extent that it fails to solve them.

For certain classes of important QP problems, and when optimization to small tolerances is not required, it's undoubtedly a great solver - but it's not a general solver.

Re: Optimization solvers: missing link for fully open-source energy system modeling

#24

Post by jvanderbot » Mon, May 02, 2022, 5:24 PM UTC

j2kun wrote: post #12

jvanderbot wrote: post #10

Where's Scip? it's performance relative to CPLEX was pretty good for the problems I threw at it.

I do datacenter optimization at Google and SCIP is ~2 orders of magnitude slower than Gurobi for our problems.

That makes sense. I don't think google can count as low as my number of optimization variables.