Not everyone wants to optimise energy to the same outcome. Some bad actors are optimising for pure profit and screw the environment, not public utility function outcomes.
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:
The problem described seems to be an ideal use-case for Machine Learning. The MATPOWER Optimal Scheduling Toolkit (MOST) can already solve:
"a stochastic, security-constrained, combined unit-commitment and multiperiod optimal power flow problem with locational contingency and load-following reserves, ramping costs and constraints, deferrable demands, lossy storage resources and uncertain renewable generation."
Much more and it becomes a global optimization problem where you can never really be sure you are not just stuck in a local optimum. The L2RPN (Learning to Run a Power Network) challenge, from RTE-France, is the most interesting effort I have seen applying Machine Learning to energy system management.
I’m in the optimization space and have never heard of this. Thanks. I recognize many of the names behind it.
I think part of the reason it’s not more popular is because QPs aren’t the most popular problem type. They’re used in MPC problems and any number of L2-loss function problems like ML problems, but these already have custom methods for solving the QP. Doesn’t meant they can’t adopt a standard high performance solver — I think this is very promising.
Also I’m not sure if there’s any political issues that limits them from listing this on COIN OR. That’s usually most folks go to site for discovering new solvers.
Yes to this! However, a while ago I tested OSQP, but I found low precision and the speed didn't justify using it over other solvers. The project remains on my radar due to the strength of the development team -- amazing group -- and knowing that numerical solvers can really shine in one domain while they struggle in others.
Another pair of projects that I find useful are ECOS [1] and CVXPY [2]. CVXPY makes head-to-head comparisons of solvers (including ECOS and OSQP) trivial.
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.
>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 significant gap in performance between HiGHS and the major commercial solvers.
It's a great need in the scientific community. Gurobi is the leading commercial solution with a strict license and a high price tag. As the proposed open-source project is only focused on linear programming (as opposed to a general nonlinear optimization), the goal may as well be achievable. Best wishes for the authors.
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)
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.
HiGHS for MIP is meaningfully faster than than SCIP after 18 months, and will get a lot better. SCIP's native LP solver is just simplex (and slower than HiGHS). For these problems you need interior point, and HiGHS is much the best open-source interior point solver for them.
There's a good reason Gurobi is so expensive, and the company hires so many stellar optimization experts. Building a top-tier solver is hard, and short of a paradigm shift I don't see this as a realistic timeline given the low funding they're asking for, and what I've heard about previous attempts to match Gurobi with far more funding.
Throwing money and people at solver projects is not the way to succeed. Get and keep the right 1-2 people, and HiGHS has already shown what is possible.
I’ve been impressed with Google’s OR-Tools CP-SAT solver which is free to use. I think I will need a good reason to us something other than a satisfiability solver on most problems. It’s a bit like the Pareto principle. You can spend a fraction of the time running a sat solver and get most of the benefit of trying to find the optimal result.
23 comments
[ 2.4 ms ] story [ 77.3 ms ] threadMain page: https://pypsa-meets-africa.github.io/highs.html
https://github.com/osqp/osqp_benchmarks
The problem described seems to be an ideal use-case for Machine Learning. The MATPOWER Optimal Scheduling Toolkit (MOST) can already solve:
"a stochastic, security-constrained, combined unit-commitment and multiperiod optimal power flow problem with locational contingency and load-following reserves, ramping costs and constraints, deferrable demands, lossy storage resources and uncertain renewable generation."
Much more and it becomes a global optimization problem where you can never really be sure you are not just stuck in a local optimum. The L2RPN (Learning to Run a Power Network) challenge, from RTE-France, is the most interesting effort I have seen applying Machine Learning to energy system management.
https://l2rpn.chalearn.org/
https://github.com/rte-france/l2rpn-baselines
The competition has been renewed for 2022 and has been accepted for the IEEE World Congress on Computational Intelligence in July.
https://wcci2022.org
I think part of the reason it’s not more popular is because QPs aren’t the most popular problem type. They’re used in MPC problems and any number of L2-loss function problems like ML problems, but these already have custom methods for solving the QP. Doesn’t meant they can’t adopt a standard high performance solver — I think this is very promising.
Also I’m not sure if there’s any political issues that limits them from listing this on COIN OR. That’s usually most folks go to site for discovering new solvers.
The domain is somewhat unique since our charging points are mobile and stochastic, but charging demand is scheduled in advance
Another pair of projects that I find useful are ECOS [1] and CVXPY [2]. CVXPY makes head-to-head comparisons of solvers (including ECOS and OSQP) trivial.
[1] https://web.stanford.edu/~boyd/papers/ecos.html
[2] https://www.cvxpy.org
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.
It's a great need in the scientific community. Gurobi is the leading commercial solution with a strict license and a high price tag. As the proposed open-source project is only focused on linear programming (as opposed to a general nonlinear optimization), the goal may as well be achievable. Best wishes for the authors.
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)