Repository files navigation

HiGHS is a high performance serial and parallel solver for large scale sparselinear optimization problems of the form

Minimize (1/2) x^TQx + c^Tx subject to L <= Ax <= U; l <= x <= u

where Q must be positive semi-definite and, if Q is zero, there may be a requirement that some of the variables take integer values. Thus HiGHS can solve linear programming (LP) problems, convex quadratic programming (QP) problems, and mixed integer programming (MIP) problems. It is mainly written in C++, but also has some C. It has been developed and tested on various Linux, MacOS and Windows installations using both the GNU (g++) and Intel (icc) C++ compilers. Note that HiGHS requires (at least) version 4.9 of the GNU compiler. It has no third-party dependencies.

HiGHS has primal and dual revised simplex solvers, originally written by Qi Huangfu and further developed by Julian Hall. It also has an interior point solver for LP written by Lukas Schork, an active set solver for QP written by Michael Feldmeier, and a MIP solver written by Leona Gottwald. Other features have been added by Julian Hall and Ivet Galabova, who manages the software engineering of HiGHS and interfaces to C, C#, FORTRAN, Julia and Python.

Although HiGHS is freely available under the MIT license, we would be pleased to learn about users' experience and give advice via email sent tohighsopt@gmail.com.

If you use HiGHS in an academic context, please acknowledge this and cite the following article.Parallelizing the dual revised simplex methodQ. Huangfu and J. A. J. HallMathematical Programming Computation, 10 (1), 119-142, 2018.DOI: 10.1007/s12532-017-0130-5

http://www.maths.ed.ac.uk/hall/HuHa13/

The project has an entry on Wikipedia:https://en.wikipedia.org/wiki/HiGHS_optimization_solver

The rest of this file gives brief documentation for HiGHS. Comprehensive documentation is available viahttps://www.highs.dev.

Precompiled static executables are available for a variety of platforms at:https://github.com/JuliaBinaryWrappers/HiGHSstatic_jll.jl/releases

These binaries are provided by the Julia community and are not officially supported by the HiGHS development team. If you have trouble using these libraries, please open a GitHub issue and tag@odow in your question.

Installation instructions

To install, download the appropriate file and extract the executable located at/bin/highs.

• For Windows users: if in doubt, choose the file ending inx86_64-w64-mingw32.tar.gz
• For M1 macOS users: choose the file ending inaarch64-apple-darwin.tar.gz
• For Intel macOS users: choose the file ending inx86_64-apple-darwin.tar.gz

Shared libaries

For advanced users, precompiled executables using shared libraries are available for a variety of platforms at:https://github.com/JuliaBinaryWrappers/HiGHS_jll.jl/releases.

Similar download instructions apply.

• These files link againstlibstdc++. If you do not have one installed, download the platform-specific libraries from:https://github.com/JuliaBinaryWrappers/CompilerSupportLibraries_jll.jl/releases/tag/CompilerSupportLibraries-v0.5.1%2B0and copy all the libraries into the same folder as thehighs executable.
• Unless using the FORTRAN interface, any of versions libgfortran3-libgfortran5 should work.If in doubt, Windows users should choose thex86_64-w64-mingw32-libgfortran5.tar.gz.

HiGHS uses CMake as build system. First setupa build folder and call CMake as follows

mkdir buildcd buildcmake -DFAST_BUILD=ON ..

Then compile the code using

cmake --build .

This installs the executablebin/highs.The minimum CMake version required is 3.15.

To perform a quick test whether the compilation was successful, run

ctest

In the following discussion, the name of the executable file generated isassumed to behighs.

HiGHS can read plain text MPS files and LP files and the following commandsolves the model inml.mps

highs ml.mps

Usage:highs [OPTION...] [file]

  --model_file arg        File of model to solve.  --presolve arg          Presolve: "choose" by default - "on"/"off" are alternatives.  --solver arg            Solver: "choose" by default - "simplex"/"ipm" are alternatives.  --parallel arg          Parallel solve: "choose" by default - "on"/"off" are alternatives.  --run_crossover arg     Run crossover after IPM: "on" by default - "choose"/"off" are alternatives.  --time_limit arg        Run time limit (seconds - double).  --options_file arg      File containing HiGHS options.  --solution_file arg     File for writing out model solution.  --write_model_file arg  File for writing out model.  --random_seed arg       Seed to initialize random number generation.  --ranging arg           Report cost, bound, RHS and basic solution ranging in any solution file: "off" by default - "on" is alternatives.  --read_solution_file    File of solution to be read    --version               Print version number

-h, --help Print help.

Note:

• If the file defines a quadratic term in the objective (so the problem is a QP or MIQP) and "simplex" or "ipm" is selected for the solver option, then the quadratic term will be ignored.
• If the file constrains some variables to take integer values and defines a quadratic term in the objective, then the problem is MIQP and cannot be solved by HiGHS

There are HiGHS interfaces for C, C#, FORTRAN, and Python in HiGHS/src/interfaces, with example driver files in HiGHS/examples.Documentation is availble viahttps://www.highs.dev/, and we are happy to give a reasonable level of support viaemail sent tohighsopt@gmail.com.

Parallel computation within HiGHS is limited to the dual simplex solver.However, performance gain is unlikely to be significant at present.For the simplex solver, at best, speed-up is limited to the number of memory channels, rather than the number of cores.

HiGHS will identify the number of available threads at run time, and restrict their use to the value of the HiGHS optionthreads.

If run withthreads=1, HiGHS is serial. The--parallel run-timeoption will cause the HiGHS parallel dual simplex solver to run in serial. Although thiscould lead to better performance on some problems, performance will typically bediminished.

If multiple threads are available, and run withthreads>1, HiGHS will use multiple threads.Although the best value will be problem and architecture dependent, for the simplex solverthreads=8 is typically agood choice.Although HiGHS is slower when run in parallel than in serial for some problems, it is typically faster in parallel.

HiGHS is compiled in a shared library. Running

make install

from the build folder installs the library inlib/, as well as all header files ininclude/. For a custominstallation ininstall_folder run

cmake -DCMAKE_INSTALL_PREFIX=install_folder ..

and then

make install

To use the library from a CMake project use

find_package(HiGHS)

and add the correct path to HIGHS_DIR.

An executable defined in the fileuse_highs.cpp (for example) is linked with the HiGHS library as follows. After running the code above, compile and run with

g++ -o use_highs use_highs.cpp -I install_folder/include/ -L install_folder/lib/ -lhighs

LD_LIBRARY_PATH=install_folder/lib/ ./use_highs

• A Julia interface is available athttps://github.com/jump-dev/HiGHS.jl.

• HiGHS can be used from rust through thehighs crate. The rust linear programming modelergood_lp supports HiGHS.

• An R interface is available through thehighs R package.

HiGHS can be used from javascript directly inside a web browser thanks tohighs-js. See thedemo and thenpm package.

Alternatively, HiGHS can directly be compiled into a single HTML file and usedin a browser. This requiresemscripten to be installed from their website(unfortunately, e.g.sudo apt install emscripten in Ubuntu Linux is broken):

https://emscripten.org/docs/getting_started/downloads.html

Then, run

sh build_webdemo.sh

This will create the filebuild_webdemo/bin/highs.html. For fast edititerations run

find src app | entr -rs 'make -C build_webdemo highs; echo'

This will rebuildhighs.html every time a source file is modified (e.g.from Visual Studio Code).

There are two ways to build the Python interface to HiGHS.

From PyPi

HiGHS has been added to PyPi, so should be installable using the command

pip install highspy

The installation can be tested using the exampleminimal.py, yielding the output

Running HiGHS 1.2.2 [date: 2022-09-04, git hash: 8701dbf19]Copyright (c) 2022 ERGO-Code under MIT licence termsPresolving model2 rows, 2 cols, 4 nonzeros0 rows, 0 cols, 0 nonzeros0 rows, 0 cols, 0 nonzerosPresolve : Reductions: rows 0(-2); columns 0(-2); elements 0(-4) - Reduced to emptySolving the original LP from the solution after postsolveModel   status      : OptimalObjective value     :  1.0000000000e+00HiGHS run time      :          0.00

or the more didacticcall_highs_from_python.py.

Directly

In order to build the Python interface, build and install the HiGHSlibrary as described above, ensure the shared library is in theLD_LIBRARY_PATH environment variable, and then run

pip install ./

fromsrc/interfaces/highspy (there should be asetup.py file there).

You may also require

• pip install pybind11
• pip install pyomo

The Python interface can then be tested as above