Английская Википедия:HiGHS optimization solver

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Шаблон:Short description

Шаблон:Use British English Шаблон:Use dmy dates

Шаблон:Infobox software

Шаблон:Infobox organization

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Шаблон:Nbspconvenient thin wrapper to Python is available via the Шаблон:Url 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Шаблон:Nnbsp[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++Шаблон:NbspAPI and other language interfaces have been developed, and modelling utilities and other categories of solver have been added.

In earlyШаблон:Nbhyph2022, 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 Шаблон:Val in funding from Invenia Labs, Cambridge, United Kingdom in JulyШаблон:Nbsp2022.[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Шаблон:Nbhyphalone solver library in bespoke applications, but numerical computing environments, optimization programming packages, and domainШаблон:Nbhyphspecific numerical analysis projects are starting to incorporate the software into their systems also.

Numerical computing support

As powerful openШаблон:Nbhyphsource 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Шаблон:Nnbsp[13] from releaseШаблон:Nbsp1.6.0Шаблон:Nnbsp[14] and the HiGHS MIP solver for discrete optimization from releaseШаблон:Nbsp1.9.0.[15] As well as offering an interface to HiGHS, the JuMP modelling language for JuliaШаблон:Nnbsp[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Шаблон:Nbhyphspecific applications, including one open energy system modeling environment. The webШаблон:Nbhyphbased version of the PyPSA European multiШаблон:Nbhyphsector model deploys the HiGHS solver by default from February 2022.[18][19] The GridCal project developing researchШаблон:Nbhyphoriented power systems software added optional support for HiGHS in FebruaryШаблон:Nbsp2022.[20]

See also

External links

References

Шаблон:Reflist


Шаблон:Mathematical optimization software Шаблон:Computer modeling

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ Ошибка цитирования Неверный тег <ref>; для сносок hall-2020 не указан текст
  2. ↑ Ошибка цитирования Неверный тег <ref>; для сносок mittelmann-benchmarks не указан текст
  3. ↑ Ошибка цитирования Неверный тег <ref>; для сносок uoe-som-oor не указан текст
  4. ↑ Ошибка цитирования Неверный тег <ref>; для сносок parzen-etal-2022 не указан текст
  5. ↑ Ошибка цитирования Неверный тег <ref>; для сносок invenia-donation не указан текст
  6. ↑ Ошибка цитирования Неверный тег <ref>; для сносок hall-and-mckinnon-2005 не указан текст
  7. ↑ Ошибка цитирования Неверный тег <ref>; для сносок huangfu-and-hall-2015 не указан текст
  8. ↑ Ошибка цитирования Неверный тег <ref>; для сносок huangfu-and-hall-2018 не указан текст
  9. ↑ Ошибка цитирования Неверный тег <ref>; для сносок mittelmann-simplex не указан текст
  10. ↑ Ошибка цитирования Неверный тег <ref>; для сносок schork-and-gondzio-2020 не указан текст
  11. ↑ Ошибка цитирования Неверный тег <ref>; для сносок mittelmann-barrier не указан текст
  12. ↑ Ошибка цитирования Неверный тег <ref>; для сносок mittelmann-mip не указан текст
  13. ↑ Ошибка цитирования Неверный тег <ref>; для сносок scipy-linprog не указан текст
  14. ↑ Ошибка цитирования Неверный тег <ref>; для сносок scipy-1.6.0-lp не указан текст
  15. ↑ Ошибка цитирования Неверный тег <ref>; для сносок scipy-1.9.0-mip не указан текст
  16. ↑ Ошибка цитирования Неверный тег <ref>; для сносок jump-home не указан текст
  17. ↑ Ошибка цитирования Неверный тег <ref>; для сносок jump-models не указан текст
  18. ↑ Ошибка цитирования Неверный тег <ref>; для сносок brown-ongoing не указан текст
  19. ↑ Ошибка цитирования Неверный тег <ref>; для сносок pypsa-server-diff-feb-2022 не указан текст
  20. ↑ Ошибка цитирования Неверный тег <ref>; для сносок gridcal-diff-feb-2022 не указан текст
Источник — http://wikihandbk.com/ruwiki/index.php?title=Английская_Википедия:HiGHS_optimization_solver&oldid=15233924