HiGHS

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.

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.

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.