## HiGHS - high performance software for linear optimization

Open source serial and parallel solver for large-scale
sparse linear programming (LP) models

## Get started

HiGHS is a high performance serial and parallel solver for large-scale sparse linear programming (LP) models developed in C++11, with interfaces to C, C#, FORTRAN, Julia and Python.

HiGHS is freely available under the MIT licence, and is downloaded from Github. Installing HiGHS from source code requires CMake minimum version 3.15, but no other third-party utilities. HiGHS can be used as a standalone executable on Windows and Linux. There is a C++11 library which can be used within a C++ project or, via one of the interfaces, to a project written in other languages.

Information on how to install and use HiGHS is given in the guide below, and full documentation can be built using doxygen. Your comments or specific questions on HiGHS would be greatly appreciated, so please send an email to highsopt@gmail.com to get in touch with the team.

HiGHS is downloaded from https://github.com/ERGO-Code/HiGHS . A simple cloned copy is obtained by the command

``  git clone git@github.com:ERGO-Code/HiGHS.git``

The latest revision (version 1.0.0) is `master`. In the instructions below on building HiGHS, running it as an executable and installing its library, HiGHS is assumed to have been downloaded to a folder called `HiGHS`.

## Guide

This guide sets out what HiGHS can be used for, and how to build and use it. HiGHS can be run from a command line or by calling it from within another application via a library.

### Specification

HiGHS can load LP models from data files or via data provided by another application. It can solve LP models using implementations of the dual revised simplex method and an interior point method. The solution can be written to a file or retrieved directly for use within an application. Within an application, HiGHS can be used to modify the current model and re-solve it efficiently.

### Building HiGHS

HiGHS uses CMake as a build system. The simplest setup is to create a build folder (within the folder into which HiGHS has been downloaded) and then build HiGHS within it. The name of the build folder is arbitrary but, assuming it is `HiGHS/build`, the full sequence of commands required is as follows

``````  mkdir build
cd build
cmake ..
make``````

This creates the executable `build/bin/highs`. To perform a quick test to see whether the compilation was successful, run `ctest` from within the build folder.

Note that HiGHS requires (at least) version 4.9 of the GNU gcc/g++ compiler.

### Running HiGHS from the command line

In the following discussion, the name of the executable file created in `build/bin` when building HiGHS is assumed to be `highs`. HiGHS can read plain text MPS files and LP files (but not compressed files), and the following command solves the model in `ml.mps`

``  highs ml.mps``

HiGHS is controlled by means of options.

### Running HiGHS from within an application

To run HiGHS from an application, the key requirements are to load a model, solve it and extract the results. Many users will want to get and set option values to control the way HiGHS runs. It is also possible to extract model data, modify a model and load a basis. HiGHS can perform other operations for specialist applications. HiGHS is linked into another application via a library.

Although HiGHS is written in C++, interfaces exist for C, C#, FORTRAN, Julia and Python. To within the limits of the language, they offer the same functionality that is available from C++, with method names that are either identical or distinguished by a consistent name extension. The discussion below refers to the C++ methods, followed by an account of the language-specific characteristics of the interfaces.

Example programs calling HiGHS from C, C#, FORTRAN, Julia and Python are in `HiGHS/examples`.

Before the C++ methods can be used, an instance of the `Highs` class must be created. Some methods are used to return data, and the others return an indication of success. In some cases this is a value of `HighsStatus`, and in others it is simply a boolean.

For full information on the detailed use of the HiGHS methods discussed below, consult the documentation built with `doxygen`. This is created by calling `doxygen` in `HiGHS/docs` and viewed by loading `HiGHS/docs/index.html` into any web browser.

The simplest way to use HiGHS to solve a model is to load a model from a file using the method `readModel`. Different file formats are recognised from the filename extension. HiGHS can read plain text MPS files and LP, but not compressed files. Alternatively, in C++, data generated by an application can be passed to HiGHS via an instance of the `HighsLp` class populated by the user and passed using the method `passModel`. An overloading of `passModel` permits the data constituting an LP model to be passed via individual parameters, and this is also possible in languages where the `HighsLp` structure cannot be used.

#### Solving a model

HiGHS is used to solve a model by calling the method `run`. By default, HiGHS minimizes the model's objective function, but this can be switched.

#### Extracting the results

After solving a model, its status is the value returned by the method `getModelStatus`. This value is of type `HighsModelStatus`, and may be interpreted via the names in the corresponding `enum`. The solution and basis are returned by the methods `getSolution` and `getBasis` respectively. Note that these are `const` references to internal data. HiGHS can also be used to write the solution to a file using the method `writeSolution`, with the output going to `stdout` if the filename is blank.

Other items of scalar information relating to the solver outcome are available by calling `getHighsInfo` to obtain a const reference to the internal `HighsInfo` structure. This gives access to the iteration counts (simplex, interior point and crossover), the status of any primal and dual solution, the objective function value, and information on any infeasibilities. Specifically, for both primal and dual, it gives the number of infeasibilities exceeding the tolerance, as well as the maximum and sum of all infeasibilities. The objective function value and simplex iteration count may also be obtained directly using the methods `getObjectiveValue` and `getSimplexIterationCount`, and this is also possible via non-C++ interfaces.

#### Extracting model data

The numbers of column, rows and nonzeros in the model are returned by the methods `getNumCols`, `getNumRows` and `getNumEntries` respectively. A const reference to the current model as an LP is returned by `getLp`. Data for subsets of columns and rows from the model may be extracted using the methods `getCols` and `getRows`, and specific matrix coefficients obtained using the method `getCoeff`.

#### Modifying a model

The most immediate model modification is to change the sense of the objective. By default, HiGHS minimizes the model's objective function. The objective sense can be set to minimize (maximize) by passing the value 1 (-1) to the method `changeObjectiveSense`. The cost coefficient or bounds of a column are changed by passing its index and new value(s) to the methods `changeColCost`, `changeColBounds`. The corresponding method for a row is `changeRowBounds`.

For the convenience of application developers, data for multiple columns and rows can be changed in three different ways in HiGHS. This is introduced in the case of column costs. The columns can be defined by the first and last indices of the interval of columns whose costs will be changed, together with the corresponding values. When costs for a non-contiguous set of columns are changed, they may be specified as a set of indices (which need not be ordered), the number of entries in the set and the corresponding values. Alternatively, the columns to be changed (not changed) may be specified by setting values of +1 (0) in an integer mask of dimension equal to the number of columns, together with a full-length vector of values. In all three cases, the method used is called `changeColsCosts`. The bounds of multiple columns or rows are changed using the methods `changeColsBounds` or `changeRowsBounds` respectively.

An individual matrix coefficient is changed by passing its row index, column index and new value to `changeCoeff`.

To add a column or row to the model, pass the necessary data to the method `addCol` or `addRow` respectively. Multiple columns and rows can be added using the methods `addCols` or `addRows`.

Columns or rows can be deleted from the model using the methods `deleteCols` or `deleteRows`. As above, the columns or rows to be deleted may be specified as a contiguous interval, a set or via a mask. In the case of the latter, the new indices of any remaining columns or rows are returned in place of the entries of 0.

Any internal basis can be over-written by calling `setBasis`. If no argument is given then an "all-slack" basis is set up internally. Otherwise, if a (valid) `HighsBasis` structire is passed, this will be used as the internal basis.

HiGHS may be run from a user-defined solution by passing it to HiGHS using the method `setSolution`.

#### Other operations

HiGHS has a suite of methods for operations with the invertible representation of the current basis matrix $B$. To use these requires knowledge of the corresponding (ordered) basic variables. This is obtained using the method `getBasicVariables`, with non-negative values being columns and negative values corresponding to row indices plus one [so -1 indicates row 0]. Methods `getBasisInverseRow` and `getBasisInverseCol` yield a specific row or column of $B-1$. Methods `getBasisSolve` and `getBasisTransposeSolve` yield the solution of $Bx=b$ and $Bx=b$ respectively. Finally, the methods `getReducedRow` and `getReducedColumn` yield a specific row or column of $B-1A$. In all cases, HiGHS can return the number and indices of the nonzeros in the result.

The incumbent model in HiGHS can be cleared by calling `clearModel`. This allows models to be built by adding variables and constraints to an empty model. It is not necessary to do this if a new model is passed to HiGHS.

The value used as infinity within HiGHS is returned by `getHighsInfinity`. The current (elapsed) run time (in seconds) of HiGHS is returned by `getHighsRunTime`.

#### Library

HiGHS may be used to create a shared library. Running

``  make install``

from the build folder attempts to install the executable in `/usr/local/bin`, the library in `/usr/local/lib`, and the header files in `/usr/local/include`. For a custom installation based in `install_folder` run

``  cmake .. -DCMAKE_INSTALL_PREFIX=install_folder``

and then

``  make install``

##### Using HiGHS in a CMake project

To use the library from a CMake project use `find_package(HiGHS)` and add the correct path to `HIGHS_DIR`.

##### Compiling and linking without CMake

An executable defined in the file `use_highs.cpp` is linked with the HiGHS library as follows. Assuming that the custom installation is based in `install_folder`, 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``````

#### Language interfaces

##### C# interface

From an application written in C#, HiGHS is run by creating a `HighsLpSolver` instance thus

``  HighsLpSolver solver = new HighsLpSolver;``

An LP model may then be read in from a file `solver.readModel`, or communicated to HiGHS by passing its component arrays of data to `HighsModel`. This returns an object that can then be passed to the `HighsLpSolver` instance via `solver.passLp`. The LP is solved using `solver.run`, and data extracted as described above for the C++ interface.

## Options

The option values that control HiGHS are of type `string`, `bool`, `int` and `double`. Options are referred to by a `string` identical to the name of their identifier. A full specification of the options is given here.

### Option values for the command line

When HiGHS is run from the command line, some fundamental option values may be specified directly. Many more may be specified via a file. Formally, the usage is

``  highs [OPTION...] [file]``

using the following options.

 `--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.` `--time_limit arg ` `Run time limit (double).` `--options_file arg ` `File containing HiGHS options.` `-h, --help ` `Print help.`

Within an options file, values are specified line-by-line as `option_name = value`. An example file containing default settings of all options is here.

Note that by setting the values of options `solution_file`, `write_solution_to_file` and `write_solution_pretty` appropriately, it is possible to write the solution to `stdout` (by setting `solution_file = ""`) or to a file in either a pretty (human-readable) or simple (computer-readable) format.

### Option values in applications

When HiGHS is run from an application, options values can be read from a file using the method `readHighsOptions`, and modified values in an instance of `HighsOptions` can be passed to HiGHS via the method `passHighsOptions`. The value of an individual option can be changed by passing its name and value to the method `setHighsOptionValue`. These methods return a `HighsStatus` error if an option name is unrecognised or the value is illegal. The current value of an option is obtained by passing its name to the method `getHighsOptionValue`.

## Background

HiGHS is based on the high performance dual revised simplex implementation (HSOL) and its parallel variant (PAMI) developed by Qi Huangfu. Features such as presolve, crash and advanced basis start have been added by Julian Hall and Ivet Galabova. Other features and the interfaces have been written by Michael Feldmeier.

### Citation

In the absence of a release paper, academic users of HiGHS are kindly requested to cite the following article

Parallelizing the dual revised simplex method, Q. Huangfu and J. A. J. Hall, Mathematical Programming Computation, 10 (1), 119-142, 2018. DOI: 10.1007/s12532-017-0130-5

## Contact

Your comments or specific questions on HiGHS would be greatly appreciated, so please send an email to highsopt@gmail.com to get in touch with the team.