HiGHS optimization solver: Difference between revisions

Revision as of 19:13, 24 July 2022

Latest revision as of 05:02, 29 June 2025

(42 intermediate revisions by 12 users not shown)

Line 1:

{{Short description|Numerical software}}

{{use British English|date=March 2022}}

{{use dmy dates|date=March 2022}}

{{infobox software

| title = HiGHS

| repo = {{url|https://github.com/ERGO-Code/HiGHS}}

| website = {{url|https://ergo-code.github.io/HiGHS}}

| programming language = [[C++]]

| license = [[MIT License|MIT]]

| genre = Optimization solver suite

| latest_release_version = 1.2.2

}}

{{infobox organization

Line 30 ⟶ 21:

| key_people = {{plainlist|

* Ivet Galabova

* Leona Gottwald

* Michael Feldmeier

}}

| num_staff = 46

| budget =

| website = {{url|https://www.highs.dev}}

}}

{{infobox software

'''HiGHS''' is open-source software to solve [[Linear_programming|linear programming]] (LP), [[Integer_programming|mixed-integer programming]] (MIP), and convex [[Quadratic_programming|quadratic programming]] (QP) models.<ref name="hall-2020"/>

| title = HiGHS

| repo = {{url|https://github.com/ERGO-Code/HiGHS}}

| website = {{url|https://ergo-code.github.io/HiGHS}}

| programming language = [[C++]]

| license = [[MIT License|MIT]]

| genre = Optimization solver suite

| latest_release_version = 1.210.20

}}

'''HiGHS''' is open-source software to solve [[Linear_programming|linear programming]] (LP), [[Integer_programmingInteger programming|mixed-integer programming]] (MIP), and convex [[Quadratic_programming|quadratic programming]] (QP) models.<ref name="hall-2020"/>

Written in [[C++]] and published under an [[MIT_License|MIT]] license, HiGHS provides programming interfaces to [[C_(programming_language)|C]], [[Python_(programming_language)|Python]], [[Julia_(programming_language)|Julia]], [[Rust (programming language)|Rust]], [[JavaScript]], [[Fortran]], and [[C_Sharp_(programming_language)|C#]]. It has no external dependencies. Although generally single-threaded, some solver components can utilize multi-core architectures. HiGHS is designed to solve large-scale models and exploits [[sparse matrix|problem sparsity]]. Its performance relative to commercial and other open-source software is reviewed periodically using industry-standard [[Benchmark (computing)|benchmarks]].<ref name="mittelmann-benchmarks"/>

Written in [[C++]] and published under an [[MIT License|MIT]] license, HiGHS provides programming interfaces to [[C (programming language)|C]], [[Python (programming language)|Python]], [[Julia (programming language)|Julia]], [[Rust (programming language)|Rust]], [[R (programming language)|R]], [[JavaScript]], [[Fortran]], and [[C Sharp (programming language)|C#]]. It has no external dependencies. A{{nbsp}}convenient thin wrapper to Python is available via the {{url|https://pypi.org/project/highspy/|highspy}} [[Python Package Index|PyPI]] package. HiGHS is also callable via [[NuGet]].<ref name="nuget-repo">

{{cite web

| title = Highs.Native

| url = https://nuget.org/packages/Highs.Native/

| access-date = 2025-05-13

}}

</ref>

Although generally single-threaded, some solver components can utilize multi-core architectures and, from {{URL|https://github.com/ERGO-Code/HiGHS/releases/tag/v1.10.0|Version 1.10.0}}, can run its first order LP solver on NVIDIA GPUs. HiGHS is designed to solve large-scale models and exploits [[sparse matrix|problem sparsity]]. Its performance relative to commercial and other open-source software is reviewed periodically using industry-standard [[Benchmark (computing)|benchmarks]].<ref name="mittelmann-benchmarks"/>

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

Line 46 ⟶ 53:

== History ==

HiGHS is based on solvers written by PhD students from the Optimization and Operational Research Group{{nnbsp}}<ref name="uoe-som-oor"/> in the School of Mathematics at the [[University_of_Edinburgh|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.<ref Since then, a C++name="galabova-2022">
{{nbsp}}[[applicationcite programming interfacethesis
|API]] andlast1 other= languageGalabova interfaces| havefirst1 been= developed, and modelling utilities and other categories of solver have been added.Ivet

| title = Presolve, crash and software engineering for HiGHS

| type = PhD

| date = 2022

| publisher = The University of Edinburgh

| ___location = Edinburgh, United Kingdom

| url = https://era.ed.ac.uk/bitstream/handle/1842/39725/GalabovaI_2022.pdf

| access-date = 2025-05-13

}}

</ref> Since then, a C++{{nbsp}}[[application programming interface|API]] and other language interfaces have been developed, and modelling utilities and other categories of solver have been added.

In early{{nbhyph}}2022, the [[open energy system models#GenX|GenX]] and [[open energy system models#PyPSA|PyPSA]] open energy system modelling projects endorsed a funding application for the HiGHS solver in an effort to reduce their [[Open Energy Modelling Initiative|community]] reliance on proprietary libraries.<ref name="parzen-etal-2022"/> That appeal resulted in {{valcurrency|amount=76000|pcode=CAD|fmt=US$gaps}} in funding from Invenia Labs, Cambridge, United Kingdom in July{{nbsp}}2022.<ref name="invenia-donation"/>

== Solvers ==

Line 54 ⟶ 72:

=== Simplex ===

HiGHS has implementations of the primal and dual [[Revised_simplex_method|revised simplex method]] for solving LP problems, based on techniques described by Hall and McKinnon (2005),<ref name="hall-and-mckinnon-2005"/> and Huangfu and Hall (2015, 2018).<ref name="huangfu-and-hall-2015"/><ref name="huangfu-and-hall-2018"/> 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.<ref name="mittelmann-simplex"/>

=== Interior point ===

HiGHS has an [[Interior-point_methodpoint method|interior point method]] implementation for solving LP problems, based on techniques described by Schork and Gondzio (2020).<ref name="schork-and-gondzio-2020"/> It is notable for solving the Newton system iteratively by a [[Conjugate_gradient_methodConjugate gradient method#The_preconditioned_conjugate_gradient_methodThe preconditioned conjugate gradient method|preconditioned conjugate gradient]] method, rather than directly, via an [[Cholesky_decompositionCholesky decomposition#LDL_decompositionLDL decomposition|LDL*]] decomposition. The interior point solver's performance relative to commercial and other open-source software is regularly reported using industry-standard benchmarks.<ref name="mittelmann-barrier"/>

=== Mixed integer programming ===

HiGHS has a [[branch and cut|branch-and-cut]] solver for MIP problems. Its performance relative to commercial and other open-source software is regularly reported using industry-standard benchmarks.<ref name="mittelmann-mip"/>

=== Quadratic programming ===

Line 74 ⟶ 92:

=== Numerical computing support ===

As powerful open{{nbhyph}}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{{nnbsp}}<ref name="scipy-linprog"/> from release{{nbsp}}1.6.0{{nnbsp}}<ref name="scipy-1.6.0-lp"/> and the HiGHS MIP solver for [[discrete optimization]] from release{{nbsp}}1.9.0.<ref name="scipy-1.9.0-mip"/> As well as offering an interface to HiGHS, the [[JuMP]] modelling language for [[Julia_Julia (programming_languageprogramming language)|Julia]]{{nnbsp}}<ref name="jump-home"/> also describes the specific use of HiGHS in its user documentation.<ref name="jump-models"/> The MIP solver in the [[NAG_Numerical_Library|NAG]] library is based on HiGHS{{nnbsp}},<ref name="nag-h02bkf"/> and HiGHS is the default LP and MIP solver in the {{nbsp}}[[MathWorks]] Optimization Toolbox{{nnbsp}}.<ref name="mathworks-R2024a"/>

=== Open energy system models ===

Line 132 ⟶ 150:

| pages = 259–283

| doi = 10.1007/s10589-005-4802-0

| s2cid = 15967632

| issn = 1573-2894

| url = http://www.optimization-online.org/DB_FILE/2000/11/234.pdf

Line 149 ⟶ 168:

| pages = 587–608

| doi = 10.1007/s10589-014-9689-1

| s2cid = 254416722

| issn = 0926-6003

| url = https://link.springer.com/content/pdf/10.1007/s10589-014-9689-1.pdf

Line 166 ⟶ 186:

| pages = 119–142

| doi = 10.1007/s12532-017-0130-5

| s2cid = 4641325

| issn = 1867-2957

| url = https://link.springer.com/content/pdf/10.1007/s12532-017-0130-5.pdf

Line 182 ⟶ 203:

| format = PDF

| doi = 10.5281/zenodo.6409432

| url = https://zenodo.org/record/6409433#.YkmpjLmxWdA

| access-date = 2022-04-03

}} Eight page funding proposal which also offers a relatively detailed roadmap. {{open access}}

Line 195 ⟶ 216:

| journal = Mathematical Programming Computation

| volume = 12

| issue = 4

| pages = 603–635

| doi = 10.1007/s12532-020-00181-8

| hdl = 20.500.11820/00a692a1-3372-41f6-8baf-f45396efcc0e

| s2cid = 53444331

| issn = 1867-2949

| url = https://link.springer.com/content/pdf/10.1007/s12532-020-00181-8.pdf

Line 215 ⟶ 239:

</ref>

<ref name="mittelmann-simplex">{{cite web

{{cite web

| title = Benchmark of Simplex LP solvers

| date = March 2022

Line 222 ⟶ 245:

| url = http://plato.asu.edu/ftp/lpsimp.html

| access-date = 2022-03-31

| archive-date = 11 November 2021

}}

| archive-url = https://web.archive.org/web/20211111222213/http://plato.asu.edu/ftp/lpsimp.html

</ref>

| url-status = dead

}}</ref>

<ref name="mittelmann-barrier">

Line 303 ⟶ 328:

| url = https://scipy.github.io/devdocs/release.1.9.0.html#highlights-of-this-release

| access-date = 2022-05-05

}}

</ref>

<ref name="nag-h02bkf">

{{cite web

| title = NAG Library Manual, Mark 29.3

| date = January 2024

| website = NAG Optimization Modelling Suite

| url = https://support.nag.com/numeric/nl/nagdoc_latest/flhtml/h/h02bkf.html

| access-date = 2024-03-25

}}

</ref>

<ref name="mathworks-R2024a">

{{cite web

| title = Optimization Toolbox Release Notes

| date = March 2024

| website = Mathworks Optimization Toolbox

| url = https://www.mathworks.com/help/optim/release-notes.html

| access-date = 2024-03-22

}}

</ref>

Line 340 ⟶ 385:

}}

<!-- templates and categories -->

{{Mathematical optimization software}}

{{Computer modeling}}

[[Category:Linear programming]]

<!-- [[Category:Mixed integer programming]] -->

<!-- [[Category:Nonlinear programming]] -->

[[Category:Free and open-source software]]

[[Category:Optimization algorithms and methods]]

[[Category:Mathematical optimization software]]

[[Category:Software using the MIT license]]

[[Category:Free software programmed in C++]]

<!-- [[Category:Quadratic programming]] -->