HiGHS optimization solver

Last updated

HiGHS
Stable release
1.7.0
Repository github.com/ERGO-Code/HiGHS
Written in C++
Type Optimization solver suite
License MIT
Website ergo-code.github.io/HiGHS
HiGHS
Headquarters Edinburgh
Location
  • United Kingdom
Director
Julian Hall
Key people
  • Ivet Galabova
Staff
3
Website www.highs.dev

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

Contents

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] The MIP solver in the NAG library is based on HiGHS , [18] and HiGHS is the default LP and MIP solver in the   MathWorks Optimization Toolbox . [19]

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. [20] [21] The GridCal project developing research‑oriented power systems software added optional support for HiGHS in February 2022. [22]

See also

Related Research Articles

<span class="mw-page-title-main">Linear programming</span> Method to solve optimization problems

Linear programming (LP), also called linear optimization, is a method to achieve the best outcome in a mathematical model whose requirements and objective are represented by linear relationships. Linear programming is a special case of mathematical programming.

<span class="mw-page-title-main">SciPy</span> Open-source Python library for scientific computing

SciPy is a free and open-source Python library used for scientific computing and technical computing.

The GNU Linear Programming Kit (GLPK) is a software package intended for solving large-scale linear programming (LP), mixed integer programming (MIP), and other related problems. It is a set of routines written in ANSI C and organized in the form of a callable library. The package is part of the GNU Project and is released under the GNU General Public License.

Computational science, also known as scientific computing, technical computing or scientific computation (SC), is a division of science that uses advanced computing capabilities to understand and solve complex physical problems. This includes

IBM ILOG CPLEX Optimization Studio is an optimization software package.

<span class="mw-page-title-main">Computational engineering</span>

Computational Engineering is an emerging discipline that deals with the development and application of computational models for engineering, known as Computational Engineering Models or CEM. Computational engineering uses computers to solve engineering design problems important to a variety of industries. At this time, various different approaches are summarized under the term Computational Engineering, including using computational geometry and virtual design for engineering tasks, often coupled with a simulation-driven approach In Computational Engineering, algorithms solve mathematical and logical models that describe engineering challenges, sometimes coupled with some aspect of AI, specifically Reinforcement Learning.

<span class="mw-page-title-main">COIN-OR</span>

Computational Infrastructure for Operations Research (COIN-OR), is a project that aims to "create for mathematical software what the open literature is for mathematical theory." The open literature provides the operations research (OR) community with a peer-review process and an archive. Papers in operations research journals on mathematical theory often contain supporting numerical results from computational studies. The software implementations, models, and data used to produce the numerical results are typically not published. The status quo impeded researchers needing to reproduce computational results, make fair comparisons, and extend the state of the art.

BARON is a computational system for solving non-convex optimization problems to global optimality. Purely continuous, purely integer, and mixed-integer nonlinear problems can be solved by the solver. Linear programming (LP), nonlinear programming (NLP), mixed integer programming (MIP), and mixed integer nonlinear programming (MINLP) are supported. In a comparison of different solvers, BARON solved the most benchmark problems and required the least amount of time per problem.

Open energy system models are energy system models that are open source. However, some of them may use third party proprietary software as part of their workflows to input, process, or output data. Preferably, these models use open data, which facilitates open science.

APOPT is a software package for solving large-scale optimization problems of any of these forms:

SAMPL, which stands for "Stochastic AMPL", is an algebraic modeling language resulting by expanding the well-known language AMPL with extended syntax and keywords. It is designed specifically for representing stochastic programming problems and, through recent extensions, problems with chance constraints, integrated chance constraints and robust optimization problems. It can generate the deterministic equivalent version of the instances, using all the solvers AMPL connects to, or generate an SMPS representation and use specialized decomposition based solvers, like FortSP.

The FICO Xpress optimizer is a commercial optimization solver for linear programming (LP), mixed integer linear programming (MILP), convex quadratic programming (QP), convex quadratically constrained quadratic programming (QCQP), second-order cone programming (SOCP) and their mixed integer counterparts. Xpress includes a general purpose non-linear solver, Xpress NonLinear, including a successive linear programming algorithm, and Artelys Knitro.

<span class="mw-page-title-main">Symbolic regression</span> Type of regression analysis

Symbolic regression (SR) is a type of regression analysis that searches the space of mathematical expressions to find the model that best fits a given dataset, both in terms of accuracy and simplicity.

<span class="mw-page-title-main">Pyomo</span>

Pyomo is a collection of Python software packages for formulating optimization models.

<span class="mw-page-title-main">JuMP</span> Programming language

JuMP is an algebraic modeling language and a collection of supporting packages for mathematical optimization embedded in the Julia programming language. JuMP is used by companies, government agencies, academic institutions, software projects, and individuals to formulate and submit optimization problems to third‑party solvers. JuMP has been specifically applied to problems in the field of operations research.

Artelys Knitro is a commercial software package for solving large scale nonlinear mathematical optimization problems.

SolverStudio is a free Excel plug-in developed at the University of Auckland that supports optimization and simulation modelling in a spreadsheet using an algebraic modeling language. It is popular in education, the public sector and industry for optimization users because it uses industry-standard modelling languages and is faster than traditional Excel optimisation approaches.

References

  1. ↑ Hall, Julian (21 September 2020). HiGHS: High-performance open-source software for linear optimization (PDF). Edinburgh, United Kingdom: University of Edinburgh. Retrieved 27 February 2022. Presentation.
  2. ↑ "Benchmarks for optimization software". Decision tree for optimization software. March 2022. Retrieved 31 March 2022.
  3. ↑ "Optimization and Operational Research: School of Mathematics". March 2022. Retrieved 31 March 2022.
  4. ↑ Parzen, Maximilian; Hall, Julian; Jenkins, Jesse; Brown, Tom (31 March 2022). Optimization solvers: the missing link for a fully open-source energy system modelling ecosystem (PDF). doi:10.5281/zenodo.6409432 . Retrieved 3 April 2022. Eight page funding proposal which also offers a relatively detailed roadmap. Open Access logo PLoS transparent.svg
  5. ↑ "A $76k donation from Invenia Labs has been received to support HiGHS". School of Mathematics, Edinburgh University. Edinburgh, Scotland. 21 July 2022. Retrieved 21 July 2022.
  6. ↑ Hall, JAJ; McKinnon, KIM (1 December 2005). "Hyper-sparsity in the revised Simplex method and how to exploit it" (PDF). Computational Optimization and Applications. 32 (3): 259–283. doi:10.1007/s10589-005-4802-0. ISSN   1573-2894. S2CID   15967632 . Retrieved 1 April 2022. Linked PDF is an early preprint.
  7. ↑ Huangfu, Q; Hall, JAJ (April 2015). "Novel update techniques for the revised simplex method" (PDF). Computational Optimization and Applications. 60 (3): 587–608. doi:10.1007/s10589-014-9689-1. ISSN   0926-6003. S2CID   254416722 . Retrieved 31 March 2022.
  8. ↑ Huangfu, Q; Hall, JAJ (1 March 2018). "Parallelizing the dual revised simplex method" (PDF). Mathematical Programming Computation. 10 (1): 119–142. doi:10.1007/s12532-017-0130-5. ISSN   1867-2957. S2CID   4641325 . Retrieved 27 February 2022. Open Access logo PLoS transparent.svg
  9. ↑ "Benchmark of Simplex LP solvers". Decision tree for optimization software. March 2022. Retrieved 31 March 2022.
  10. ↑ Schork, Lukas; Gondzio, Jacek (December 2020). "Implementation of an interior point method with basis preconditioning" (PDF). Mathematical Programming Computation. 12 (4): 603–635. doi:10.1007/s12532-020-00181-8. hdl:20.500.11820/00a692a1-3372-41f6-8baf-f45396efcc0e. ISSN   1867-2949. S2CID   53444331 . Retrieved 31 March 2022.
  11. ↑ "Benchmark of Barrier LP solvers". Decision tree for optimization software. March 2022. Retrieved 31 March 2022.
  12. ↑ "The MIPLIB2017 Benchmark Instances". Decision tree for optimization software. March 2022. Retrieved 31 March 2022.
  13. ↑ "SciPy — scipy.optimize.linprog". SciPy Optimization. March 2022. Retrieved 1 April 2022.
  14. ↑ "SciPy — Release 1.6.0 Highlights". SciPy Optimization. March 2022. Retrieved 2 April 2022.
  15. ↑ "SciPy — Release 1.9.0 Highlights". SciPy Optimization. May 2022. Retrieved 5 May 2022.
  16. ↑ "JuMP". JuMP. March 2022. Retrieved 1 April 2022.
  17. ↑ "JuMP — Models". JuMP. March 2022. Retrieved 1 April 2022.
  18. ↑ "NAG Library Manual, Mark 29.3". NAG Optimization Modelling Suite. January 2024. Retrieved 25 March 2024.
  19. ↑ "Optimization Toolbox Release Notes". Mathworks Optimization Toolbox. March 2024. Retrieved 22 March 2024.
  20. ↑ Brown, Tom. "PyPSA-Eur-Sec optimization server" . Retrieved 22 July 2022. A web interface to PyPsa‑Eur‑Sec model.
  21. ↑ "GitHub commit: Switch solver from Gurobi to HiGHS". PyPSA server project. 3 February 2022. Retrieved 22 July 2022.
  22. ↑ "GitHub commit: Added Highs for linux". GridCal project. 3 February 2022. Retrieved 24 July 2022.


This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.