**HiGHS** - high performance
software

for linear optimization

sparse linear programming (LP),

mixed-integer programming (MIP), and quadratic programming (QP) models

## Get started

HiGHS is high performance serial and parallel software for solving large-scale sparse linear programming (LP), mixed-integer programming (MIP) and quadratic programming (QP) 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 stand-alone executable on Windows, Linux and MacOS. 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. The guide makes minimal use of technical terms, and these will be familiar to users who have studied linear optimization. However, for those who are modelling linear optimization problems and just want a solution, the terms are defined in the terminology section.

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.

## Download

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.1.1) 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 and MIP 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, and MIP models using branch-and-bound. 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.

#### Loading a model

The simplest way to use HiGHS to solve a model is to load a it 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 `HighsModel`

class populated by the user
and passed using the
method `passModel`

. A `HighsModel`

instance
consists of an instance of the `HighHessian`

class, and an
instance of the `HighsLp`

class. As the name suggests, the
former contains the data for any quadratic term in the objective
function, and the latter the contains the remainder of the model,
including any integrality restrictions on variables. A purely linear
model can be passed to HiGHS as an instance of
the `HighsLp`

class via an overloading
of `passModel`

. Another overloading
of `passModel`

permits the data constituting a 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 `getInfo`

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 may also be obtained
directly using the method `getObjectiveValue`

, and this is
also possible via non-C++ interfaces.

#### Extracting model data

A const reference to the current internal `HighsModel`

instance is returned by the method `getModel`

, and a
const reference to the current internal `HighsLp`

instance 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.

#### Loading a basis or solution

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`

structure 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. |

Note that if the `solver`

options is set
to `"simplex"`

or `"ipm"`

then a MIP that is
read into HiGHS, or passed via `passModel`

, will be solved
as an LP.

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`

,
it is possible to write the solution to a file or, by
setting `solution_file = ""`

, to `stdout`

. By
default the solution is written in a simple (computer-readable) format
but, by setting `write_solution_style=1`

, it is written in
a pretty (human-readable) format.

### Option values in applications

When HiGHS is run from an application, options values can be read
from a file using the method `readOptions`

, and modified
values in an instance of `HighsOptions`

can be passed to
HiGHS via the method `passOptions`

. The value of an
individual option can be changed by passing its name and value to the
method `setOptionValue`

. 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 `getOptionValue`

.

## Background

### Authorship

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. The QP solver and original language interfaces were written by Michael Feldmeier. Leona Gottwald wrote the MIP solver. The software engineering of HiGHS was developed by Ivet Galabova.

### 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

### Terminology

Any linear optimization problem will have **decision
variables**, a linear or quadratic **objective
function**, and linear **constraints**
and **bounds** on the values of the decision
variables. A **mixed-integer** optimization problem will
require some or all of the decision variables to take integer
values. The problem may require the objective function to be maximized
or minimized whilst satisfying the constraints and bounds. By
default, HiGHS minimizes the objective function.

The bounds on a decision variable are the least and greatest values
that it may take, and infinite bounds can be specified. A linear
objective function is given by a set of coefficients, one for each
decision variable, and its value is the sum of products of
coefficients and values of decision variables. The objective
coefficients are often referred to as **costs**, and some
may be zero. When a problem has been solved, the optimal values of the
decision variables are referred to as the **(primal)
solution**.

Linear constraints require linear functions of decision variables
to lie between bounds, and infinite bounds can be specified. If the
bounds are equal, then the constraint is
an **equation**. If the bounds are both finite, then the
constraint is said to be **boxed**
or **two-sided**.

The coefficients of the linear constraints are naturally viewed as
rows of a **matrix**. The constraint coefficients
associated with a particular decision variable form a column of the
constraint matrix. Hence constraints are sometimes referred to
as **rows**, and decision variables
as **columns**. Constraint matrix coefficients may be
zero. Indeed, for large practical problems it is typical for most of
the coefficients to be zero. When this property can be exploited to
computational advantage, the matrix is said to
be **sparse**. When the constraint matrix is not sparse,
the solution of large problems is normally intractable
computationally.

It is possible to define a set of constraints and bounds that
cannot be satisfied, in which case the problem is said to
be **infeasible**. Conversely, it is possible that the
value of the objective function can be improved without bound whilst
satisfying the constraints and bounds, in which case the problem is
said to be **unbounded**. If a problem is neither
infeasible, nor unbounded, it has an **optimal
solution**. The optimal objective function value for a linear
optimization problem may be achieved at more than point, in which case
the optimal solution is said to be **non-unique**.

When none of the decision variables is required to take integer
values, the problem is said to be **continuous**. For
continuous problems, each variable and constraint has an
associated **dual variable**. The values of the dual
variables constitute the **dual solution**, and it is for
this reason that the term **primal solution** is used to
distinguish the optimal values of the decision variables. At the
optimal solution of a continuous problem, some of the decision
variables and values of constraint functions will be equal to their
lower or upper bounds. Such a bound is said to
be **active**. If a variable or constraint is at a bound,
its corresponding dual solution value will generally be non-zero: when
at a lower bound the dual value will be non-negative; when at an upper
bound the dual value will be non-positive. When maximizing the
objective the required signs of the dual values are reversed. Due to
their economic interpretation, the dual values associated with
constraints are often referred to as **shadow prices**
or **fair prices**. Mathematically, the dual values
associated with variables are often referred to as **reduced
costs**, and the dual values associated with constraints are
often referred to as **Lagrange multipliers**.

Analysis of the change in optimal objective value of a continuous
linear optimization problem as the cost coefficients and bounds are
changed is referred to in HiGHS as **ranging**. For an
active bound, the corresponding dual value gives the change in the
objective if that bound is increased or decreased. This level of
analysis is often referred to as **sensitivity**. In
general, the change in the objective is only known for a limited range
of values for the active bound. HiGHS will return the limits of
these **bound ranges** ranges, the objective value at
both limits and the index of a variable or constraint that will
acquire an active bound at both limits. For each variable with an
active bound, the solution will remain optimal for a range of values
of its cost coefficient. HiGHS will return the values of
these **cost ranges**. For a variable or constraint whose
value is not at a bound, HiGHS will return the range of values that
the variable or constraint can take, the objective values at the
limits of the range, and the index of a variable or constraint with a
bound that will become in active at both limits.

## The Team

## 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.