HiGHS is open-source software to solve

linear programming Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships. Linear programming is ...

(LP), mixed-integer programming (MIP), and convex

quadratic programming Quadratic programming (QP) is the process of solving certain mathematical optimization problems involving quadratic functions. Specifically, one seeks to optimize (minimize or maximize) a multivariate quadratic function subject to linear constr ...

(QP) models. Written in C++ and published under an

MIT The Massachusetts Institute of Technology (MIT) is a private land-grant research university in Cambridge, Massachusetts. Established in 1861, MIT has played a key role in the development of modern technology and science, and is one of the ...

license, HiGHS provides programming interfaces to C, Python,

Julia Julia is usually a feminine given name. It is a Latinate feminine form of the name Julio and Julius. (For further details on etymology, see the Wiktionary entry "Julius".) The given name ''Julia'' had been in use throughout Late Antiquity (e ...

Rust Rust is an iron oxide, a usually reddish-brown oxide formed by the reaction of iron and oxygen in the catalytic presence of water or air moisture. Rust consists of hydrous iron(III) oxides (Fe2O3·nH2O) and iron(III) oxide-hydroxide (FeO(OH), ...

JavaScript JavaScript (), often abbreviated as JS, is a programming language that is one of the core technologies of the World Wide Web, alongside HTML and CSS. As of 2022, 98% of Website, websites use JavaScript on the Client (computing), client side ...

, Fortran, and 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 problem sparsity. Its performance relative to commercial and other open-source software is reviewed periodically using industry-standard benchmarks. 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 in the School of Mathematics at the

University of Edinburgh The University of Edinburgh ( sco, University o Edinburgh, gd, Oilthigh Dhùn Èideann; abbreviated as ''Edin.'' in post-nominals) is a public research university based in Edinburgh, Scotland. Granted a royal charter by King James VI in 15 ...

. 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 An application programming interface (API) is a way for two or more computer programs to communicate with each other. It is a type of software interface, offering a service to other pieces of software. A document or standard that describes how ...

and other language interfaces have been developed, and modelling utilities and other categories of solver have been added. In early2022, the

GenX The General Electric GEnx ("General Electric Next-generation") is an advanced dual rotor, axial flow, high-bypass turbofan jet engine in production by GE Aviation for the Boeing 787 and 747-8. The GEnx is intended to succeed the CF6 in GE's p ...

and PyPSA open energy system modelling projects endorsed a funding application for the HiGHS solver in an effort to reduce their

community A community is a social unit (a group of living things) with commonality such as place, norms, religion, values, customs, or identity. Communities may share a sense of place situated in a given geographical area (e.g. a country, villag ...

reliance on proprietary libraries. That appeal resulted in in funding from Invenia Labs, Cambridge, United Kingdom in July2022.

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), and Huangfu and Hall (2015, 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.

Interior point

HiGHS has an

interior point method Interior-point methods (also referred to as barrier methods or IPMs) are a certain class of algorithms that solve linear and nonlinear convex optimization problems. An interior point method was discovered by Soviet mathematician I. I. Dikin in 1 ...

implementation for solving LP problems, based on techniques described by Schork and Gondzio (2020). 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.

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.

Quadratic programming

HiGHS has an active set solver for convex

(QP) problems.

Applications using HiGHS

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

Numerical computing support

As powerful opensource software under active development, HiGHS is increasingly being adopted by

application software Application may refer to: Mathematics and computing * Application software, computer software designed to help the user to perform specific tasks ** Application layer, an abstraction layer that specifies protocols and interface methods used in a ...

projects that provide support for

numerical analysis Numerical analysis is the study of algorithms that use numerical approximation (as opposed to symbolic manipulations) for the problems of mathematical analysis (as distinguished from discrete mathematics). It is the study of numerical methods th ...

. The

SciPy SciPy (pronounced "sigh pie") is a free and open-source Python library used for scientific computing and technical computing. SciPy contains modules for optimization, linear algebra, integration, interpolation, special functions, FFT, signal ...

scientific library, for instance, uses HiGHS as its LP solver from release1.6.0 and the HiGHS MIP solver for

discrete optimization Discrete optimization is a branch of optimization in applied mathematics and computer science. Scope As opposed to continuous optimization, some or all of the variables used in a discrete mathematical program are restricted to be discrete var ...

from release1.9.0. As well as offering an interface to HiGHS, the

JuMP Jumping is a form of locomotion or movement in which an organism or non-living (e.g., robotic) mechanical system propels itself through the air along a ballistic trajectory. Jump or Jumping also may refer to: Places * Jump, Kentucky or Jump S ...

modelling language for

also describes the specific use of HiGHS in its user documentation.

Open energy system models

HiGHS is now also used by some domainspecific applications, including one open energy system modeling environment. The webbased version of the PyPSA European multisector model deploys the HiGHS solver by default from February 2022. The GridCal project developing researchoriented power systems software added optional support for HiGHS in February2022.

External links

GitHub repository

Software documentation

References

{{Computer modeling Linear programming Free and open-source software Optimization algorithms and methods