Organization:HiGHS optimization solver

From HandWiki
Short description: Numerical software


HiGHS
Stable release
1.5.3
Repositorygithub.com/ERGO-Code/HiGHS
Written inC++
TypeOptimization solver suite
LicenseMIT
Websiteergo-code.github.io/HiGHS
HiGHS
HiGHS Icon.jpg
HeadquartersEdinburgh
Location
  • United Kingdom
Director
Julian Hall
Key people
  • Ivet Galabova
Staff
3
Websitewww.highs.dev

HiGHS is open-source software to solve linear programming (LP), mixed-integer programming (MIP), and convex quadratic programming (QP) models.[1]

Written in C++ and published under an MIT license, HiGHS provides programming interfaces to C, Python, Julia, Rust, JavaScript, Fortran, and C#. It has no external dependencies. A convenient thin wrapper to Python is available via the highspy PyPI package.

Although generally single-threaded, some solver components can utilize multi-core architectures. HiGHS is designed to solve large-scale models and exploits problem sparsity. Its performance relative to commercial and other open-source software is reviewed periodically using industry-standard benchmarks.[2]

The term HiGHS may also refer to both the underlying project and the small team leading the software development.

History

HiGHS is based on solvers written by PhD students from the Optimization and Operational Research Group [3] in the School of Mathematics at the University of Edinburgh. Its origins can be traced back to late 2016, when Ivet Galabova combined her LP presolve with Julian Hall's simplex crash procedure and Huangfu Qi's dual simplex solver to solve a class of industrial LP problems faster than the best open-source solvers at that time. Since then, a C++ API and other language interfaces have been developed, and modelling utilities and other categories of solver have been added.

In early‑2022, the GenX and PyPSA open energy system modelling projects endorsed a funding application for the HiGHS solver in an effort to reduce their community reliance on proprietary libraries.[4] That appeal resulted in CAN$76000 in funding from Invenia Labs, Cambridge, United Kingdom in July 2022.[5]

Solvers

Simplex

HiGHS has implementations of the primal and dual revised simplex method for solving LP problems, based on techniques described by Hall and McKinnon (2005),[6] and Huangfu and Hall (2015, 2018).[7][8] These include the exploitation of hyper-sparsity when solving linear systems in the simplex implementations and, for the dual simplex solver, exploitation of multi-threading. The simplex solver's performance relative to commercial and other open-source software is regularly reported using industry-standard benchmarks.[9]

Interior point

HiGHS has an interior point method implementation for solving LP problems, based on techniques described by Schork and Gondzio (2020).[10] It is notable for solving the Newton system iteratively by a preconditioned conjugate gradient method, rather than directly, via an LDL* decomposition. The interior point solver's performance relative to commercial and other open-source software is regularly reported using industry-standard benchmarks.[11]

Mixed integer programming

HiGHS has a branch-and-cut solver for MIP problems. Its performance relative to commercial and other open-source software is regularly reported using industry-standard benchmarks.[12]

Quadratic programming

HiGHS has an active set solver for convex quadratic programming (QP) problems.

Applications using HiGHS

HiGHS can be used as a stand‑alone solver library in bespoke applications, but numerical computing environments, optimization programming packages, and domain‑specific numerical analysis projects are starting to incorporate the software into their systems also.

Numerical computing support

As powerful open‑source software under active development, HiGHS is increasingly being adopted by application software projects that provide support for numerical analysis. The SciPy scientific library, for instance, uses HiGHS as its LP solver [13] from release 1.6.0 [14] and the HiGHS MIP solver for discrete optimization from release 1.9.0.[15] As well as offering an interface to HiGHS, the JuMP modelling language for Julia [16] also describes the specific use of HiGHS in its user documentation.[17]

Open energy system models

HiGHS is now also used by some domain‑specific applications, including one open energy system modeling environment. The web‑based version of the PyPSA European multi‑sector model deploys the HiGHS solver by default from February 2022.[18][19] The GridCal project developing research‑oriented power systems software added optional support for HiGHS in February 2022.[20]

See also

External links

References

  1. ↑ Hall, Julian (21 September 2020). HiGHS: High-performance open-source software for linear optimization. Edinburgh, United Kingdom: University of Edinburgh. https://co-at-work.zib.de/slides/Montag_21.9/HiGHS%20slides%20%281%29.pdf. Retrieved 2022-02-27.  Presentation.
  2. ↑ "Benchmarks for optimization software". March 2022. http://plato.asu.edu/bench.html. 
  3. ↑ "Optimization and Operational Research: School of Mathematics". March 2022. https://www.maths.ed.ac.uk/school-of-mathematics/research/data-decisions/optimization-and-operational-research. 
  4. ↑ Parzen, Maximilian; Hall, Julian; Jenkins, Jesse; Brown, Tom (31 March 2022) (PDF). Optimization solvers: the missing link for a fully open-source energy system modelling ecosystem. doi:10.5281/zenodo.6409432. https://zenodo.org/record/6409433. Retrieved 2022-04-03.  Eight page funding proposal which also offers a relatively detailed roadmap. open access
  5. ↑ "A $76k donation from Invenia Labs has been received to support HiGHS". School of Mathematics, Edinburgh University. Edinburgh, Scotland. 21 July 2022. https://www.maths.ed.ac.uk/school-of-mathematics/news?nid=974. 
  6. ↑ Hall, JAJ; McKinnon, KIM (1 December 2005). "Hyper-sparsity in the revised Simplex method and how to exploit it". Computational Optimization and Applications 32 (3): 259–283. doi:10.1007/s10589-005-4802-0. ISSN 1573-2894. http://www.optimization-online.org/DB_FILE/2000/11/234.pdf. Retrieved 2022-04-01.  Linked PDF is an early preprint.
  7. ↑ Huangfu, Q; Hall, JAJ (April 2015). "Novel update techniques for the revised simplex method". Computational Optimization and Applications 60 (3): 587–608. doi:10.1007/s10589-014-9689-1. ISSN 0926-6003. https://link.springer.com/content/pdf/10.1007/s10589-014-9689-1.pdf. Retrieved 2022-03-31. 
  8. ↑ Huangfu, Q; Hall, JAJ (1 March 2018). "Parallelizing the dual revised simplex method". Mathematical Programming Computation 10 (1): 119–142. doi:10.1007/s12532-017-0130-5. ISSN 1867-2957. https://link.springer.com/content/pdf/10.1007/s12532-017-0130-5.pdf. Retrieved 2022-02-27.  open access
  9. ↑ "Benchmark of Simplex LP solvers". March 2022. http://plato.asu.edu/ftp/lpsimp.html. 
  10. ↑ Schork, Lukas; Gondzio, Jacek (December 2020). "Implementation of an interior point method with basis preconditioning". Mathematical Programming Computation 12 (4): 603–635. doi:10.1007/s12532-020-00181-8. ISSN 1867-2949. https://link.springer.com/content/pdf/10.1007/s12532-020-00181-8.pdf. Retrieved 2022-03-31. 
  11. ↑ "Benchmark of Barrier LP solvers". March 2022. http://plato.asu.edu/ftp/lpbar.html. 
  12. ↑ "The MIPLIB2017 Benchmark Instances". March 2022. http://plato.asu.edu/ftp/milp.html. 
  13. ↑ "SciPy — scipy.optimize.linprog". March 2022. https://scipy.github.io/devdocs/reference/generated/scipy.optimize.linprog.html. 
  14. ↑ "SciPy — Release 1.6.0 Highlights". March 2022. https://docs.scipy.org/doc/scipy/release.1.6.0.html#highlights-of-this-release. 
  15. ↑ "SciPy — Release 1.9.0 Highlights". May 2022. https://scipy.github.io/devdocs/release.1.9.0.html#highlights-of-this-release. 
  16. ↑ "JuMP". March 2022. https://jump.dev. 
  17. ↑ "JuMP — Models". March 2022. https://jump.dev/JuMP.jl/stable/manual/models. 
  18. ↑ Brown, Tom. "PyPSA-Eur-Sec optimization server". https://model.energy/scenarios/.  A web interface to PyPsa‑Eur‑Sec model.
  19. ↑ "GitHub commit: Switch solver from Gurobi to HiGHS". PyPSA server project. 3 February 2022. https://github.com/PyPSA/pypsa-server/commit/1f1ffad8fb52aea117c771132e7236516cd458bb. 
  20. ↑ "GitHub commit: Added Highs for linux". GridCal project. 3 February 2022. https://github.com/SanPen/GridCal/commit/0d943e553649fcd6f5840a60e10ed35f0a316c64. 




Retrieved from "https://handwiki.org/wiki/index.php?title=Organization:HiGHS_optimization_solver&oldid=3391261"