Open source HiGHS solver & performance boost for energy system models

[MaxParzen]

Dear Openmodders,
We recently integrated the open-source HiGHS solver into PyPSA (see PR) and observed an incredible performance boost compared to alternatives. Promising is that the HiGHS solver team is actively improving the solver whereas most other open-source solver communities stopped developments.

Further performance check:

• 1year, 3h resolution, (~2920 snapshots), 3 nodes: CBC/CLP ~14min, HiGHS ~8min, Gurobi ~1min
• 1year, 1h resolution, (~8760 snapshots), 3 nodes: CBC/CLP ~130min, HiGHS 50min, Gurobi ~1min

To benefit the whole community, PyPSA colleagues are working on Linopy - a more generalised solver interface that is tailored for energy system models. This general interface will include HiGHS and other open and closed source solvers. One can say it’s a successor of Pyomo for these specific problem types as it accelerates the speed through harnessing the power of xarray, pandas, dask. Its official 0.1.0 release is coming very soon.

Open source solvers still can’t properly deal with long-timeseries problems. While we observed an extreme speed boost for short time series, this holds not true for longer time series. Gurobi solves in 1min an investment and dispatch problem with DCOPF that contains 5 nodes, 1 year, and hourly resolution, while HiGHS and others may need 2+ hours. This performance drop can occur because of dense-columns issues or other problems. Such bottlenecks can be removed by supporting the developer community behind the tools. For instance, the HiGHS team is currently searching for funding to further improve the IPM solver.

Thank you to @fabian.neumann , @lisa.zeyen , @fabianhofmann (PyPSA team) for supporting this development during the research visit at @tom_brown group. Thank you also to Julian Hall and Leona Gottwald (HiGHS team) for the interesting discussion. Finally, also thank you Daniel Rehfeldt (PIPS-IPM++) for the invite and discussion at the ZUSE Institute Berlin.

BR, Max
PyPSA meets Africa
University of Edinburgh

[fabian.neumann]

Just a few words of caution to add to this:

• Linopy is not planned as a full alternative to pyomo. It’s currently only planned for LP and MILP problems with a more limited feature set than pyomo but tailored for limited memory consumption.

• The performance of HiGHS for these medium-sized problems is quite impressive compared to other open-source alternatives and could be very useful for dispatch problems. For large combined investment and dispatch problems, it cannot yet compete with the commercial solvers. Here, Max solved a co-optimisatoin investment problem of generation, storage and transmission with the default PyPSA-Eur configuration with around 200-250 snapshots.

My practical wishlist for the HiGHS dev team would be regular tags in their Github repository.

[alexkies]

Hi Max, this is interesting work. I feel like there is also some dependency regarding preprocessing, scaling, parameter choices etc. which effect run times. Are in all cases default parameters and options used?
This could be an interesting machine learning task to map parameters / initial values / scaling, etc. to runtime.
Can somebody back this up with more profound theoretical knowledge?

[robbie.morrison]

Not sure what the overlap might be, but this SMS++ dedicated energy system solver library written in C++17 appears perhaps related:

• Frangioni, Antonio and Sandrine Charousset (28 October 2021). plan4res SMS++: an open modelling library for evaluating long term electricity system costs and flexibilities. Italy: University of Pisa. EMP‑E 2021 presentation. Open access.

I also understand SMS++ is formulated to be general (like AMPL or JuMP), although its development was funded through applications for energy system analysis. See GitLab and related documentation. Note also this UCBlock unit commitment specialization.

[MaxParzen]

Hi @alexkies , would be interesting to see how much parameter tuning can speed up things. We use mostly default values and only slightly deviate from the default tolerance. These are the parameters probably interesting for a tuning task:

    "primal_feasibility_tolerance": 1e-04,
    "dual_feasibility_tolerance": 1e-05,
    "ipm_optimality_tolerance": 1e-6,
    "threads": 4,

Further, the above results were tested with crossover = True. We know that the crossover is quite time consuming and can be deactivated for our problem. The HiGHS team just shared a branch that will be soon merged into the main that allows deactivating the crossover.

I guess the bottlenecks causing the slow speed for large problems (1 year, hourly resolution 200nodes+) are not in the parameter choice but more in the used methods and code implementations. Some work to investigate this is required for finding and fixing the bottlenecks.

Regarding scaling, we discussed recently the topic here: https://github.com/PyPSA/PyPSA/issues/309
“HiGHS can perform a range of industry-standard scaling techniques, and scaling is always performed if it is felt to be worthwhile. Alternatives to the default are easily specified. Problem-specific scaling may be worth considering , although aggressive scaling has some disadvantages, so shouldn’t be seen as a panacea.” - Julian Hall

[alexkies]

@MaxParzen

I guess the bottlenecks causing the slow speed for large problems (1 year, hourly resolution 200nodes+) are not in the parameter choice but more in the used methods and code implementations. Some work to investigate this is required for finding and fixing the bottlenecks.

@MaxParzen I fully agree,but this is probably rather complex. These open source solvers are so much worse for a reason … Could your discussions with these optimization experts shine some light on this if there is hope for these bottlenecks to be identified and removed?

[MaxParzen]

Hi @alexkies , there is hope and much more hope since the developers of HiGHs are quite active. I know that time is an issue for the HiGHs team. They need to find time to find the bottlenecks, to fix them or assign PhD or postdocs to fix them. Since the project is open-source locating people outside of the hosting institution might help improve the solver as well in a reasonable time. This would require us modellers to find funding for people that want to improve open source solvers i.e. ZUSE institute Berlin or similar for our type of problems. I hope we get there.

[JuhaKiviluoma]

Hello Max. Very nice post. This is LP, right? Have you thought about comparing CLP? At least it’s much better than GLPK.

[MaxParzen]

Hi @JuhaKiviluoma, thanks for that questions. Yes it’s a LP problem. CBC is running CLP under the hood, see Cbc and Clp performance - Optimization (Mathematical) - JuliaLang so there is no need for another run (CBC in PyPSA is really just a naming convention as we can solve MIP and LP). Seems for that specific time-scale and spatial resolution that GLPK was performing better than Cbc/Clp with the default configurations. The performance results might change when looking at other time scales, using different solver configs etc.

I will update this evening some results on the “further performance check” to investigate the solver performance for a bit longer timeseries.

[MaxParzen]

Update. The HiGHS dev team wants to address the performance bottlenecks in particular for our energy system modelling type of problems class. If someone is aware of 5-digit number funding for 6-12 months development, please reach out to me or the HiGHS dev team.
FYI, @robbie.morrison @alexkies
My email: max.parzen(<@>)ed.ac.uk

[robbie.morrison]

Just adding some related references:

• Hall, Julian (21 September 2020). HiGHS: High-performance open-source software for linear optimization. Edinburgh, United Kingdom: University of Edinburgh. Presentation.

• Huangfu, Q and JAJ Hall (1 March 2018). “Parallelizing the dual revised simplex method”. Mathematical Programming Computation. 10 (1): 119–142. ISSN 1867-2957. doi:10.1007/s12532-017-0130-5.

[robbie.morrison]

A new webpage detailing efforts to secure funding for the HiGHS project (with some effort the embedded PDF containing a funding application can be downloaded too):

PyPSA meets Africa - An open energy system model initiative for Africa.

[ludwig.huelk]

I am currently updating and extending the ontology class solver in the OEO:

Restructuring individuals: solver

I queried the OEP Model Factsheets to include all used solvers and compiled a first version of the definitions. Feel free to comment and add your suggestions!

[MaxParzen]

Big news. HiGHS got USD $76 000 (circa €75 000) funding. See the post on LinkedIn: Maximilian Parzen on LinkedIn: #free #opensource #supports. Just now they were awarded another 35k€ from FONDATION MATHEMATIQUE JACQUES HADAMARD (FMJH) What a day! They need more of these numbers on a yearly basis to keep their work going and grow sustainably.

[robbie.morrison]

For the record, now on wikipedia too: https://en.wikipedia.org/wiki/HiGHS_optimization_solver

[MaxParzen]

Another 420k$ for the open-source solver HiGHS. More infos will follow soon. https://twitter.com/HighsOpt/status/1556983177402531841

This will help solving practical relevant energy planning problems with open-source optimization solvers. Is your organisation also using optimization? If yes, maybe it might make sense to join and sustainably fund this great team.