HiGHS Solver Documentation

HiGHS provides several fundamental structures to represent the state and results of an optimization problem. The core structures available for end-user interaction include:

• HighsSolution: Represents the solution found by the solver (e.g., variable values).
• HighsBasis: Represents the basis of the solution, typically used in simplex-based methods.
• HighsInfo: Provides metadata and status information about the solver and the current problem state.
• HighsLinearObjective: Describes the linear objective function of the optimization problem.

Note that structure data members intended for internal solver use are not exposed in this documentation.

HiGHS provides optimization features through several language interfaces. Most users can find sufficient functionality in the basic and further guide sections, which primarily use the highspy Python interface as a reference.

Supported interfaces include:

• Python (via highspy)
• C++
• C
• C#
• Fortran

While the documentation often uses highspy method names for examples, the underlying functionality and method names in other interfaces (C++, C, C#, Fortran) are designed to be as similar as possible. Advanced features not available in highspy are specifically covered in the advanced section for C++, C, and Fortran users.

HiGHS is a high-performance serial and parallel solver for large-scale sparse linear optimization problems. It supports:

• Linear Programming (LP)
• Convex Quadratic Programming (QP)
• Mixed Integer Programming (MIP)

It is designed to solve problems of the form: $$\min \quad \dfrac{1}{2}x^TQx + c^Tx \qquad \textrm{s.t.}~ \quad L \leq Ax \leq U; \quad l \leq x \leq u$$ where $Q$ is positive semi-definite. The software is primarily written in C++ and is available for Linux, MacOS, and Windows with no third-party dependencies required.

When using cuPDLP-c via HiGHS, infeasible and unbounded LPs are identified and returned with the status INFEASIBLE_OR_UNBOUNDED.

In the case of unbounded LPs, cuPDLP-c identifies a primal feasible point, allowing it to deduce unboundedness.

HiGHS distinguishes between two types of solution values in continuous models:

Primal Values

These are the optimal values of the decision variables themselves.

Dual Values

For continuous models, every variable and constraint has an associated dual value. These constitute the dual solution.

• For Constraints: Dual values are often called shadow prices or fair prices (mathematically, Lagrange multipliers).
• For Variables: Dual values are often called reduced costs.

Active Bounds: At the optimal solution, if a variable or constraint is equal to its lower or upper bound, that bound is considered active. An active bound generally results in a non-zero dual value.

Discrete optimization problems (MIP) do not have local optimality conditions. Integer requirements are enforced within a mip_feasibility_tolerance.

Important Note on MIP Tolerances: When solving MIP problems, the standard LP feasibility tolerances set by the user are ignored. Instead, the MIP solver uses:

• primal_feasibility_tolerance = mip_feasibility_tolerance
• dual_feasibility_tolerance = $0.1 \times$ mip_feasibility_tolerance

The HighsSparseMatrix class is used to communicate the constraint matrix of a Linear Programming (LP) model. It uses a compressed storage format (typically Compressed Sparse Column or similar) to represent the non-zero elements of the matrix efficiently.

To construct or interpret a matrix, you must provide the following fields:

• format_: The MatrixFormat type indicating how the matrix is structured.
• num_col_: The total number of columns in the matrix.
• num_row_: The total number of rows in the matrix.
• start_: An integer vector indicating the starting position of each compressed vector.
• index_: An integer vector containing the indices of the non-zero elements.
• value_: A double vector containing the actual values of the non-zero elements.

HiGHS provides ranging (sensitivity analysis) for continuous linear optimization models to show how changes in cost coefficients and bounds affect the optimal objective value.

Bound Ranging

For an active bound, HiGHS returns:

• The bound ranges (the limits within which the bound can change while maintaining the current optimal basis).
• The objective value at both limits.
• The index of a variable or constraint that will acquire an active bound at both limits.

For variables/constraints not at a bound, HiGHS returns the range of values they can take and the objective values at the limits.

Cost Ranging

For each variable with an active bound, HiGHS returns the cost ranges: the range of values for the variable's cost coefficient for which the current solution remains optimal.

The minimal usage of HiGHS follows a three-stage lifecycle:

1. Define a model: Create the mathematical model by reading a file or building it via API calls.
2. Solve the model: Execute the solver using the run method.
3. Extract results: Retrieve the model status, objective value, and solution variables.

While default settings work for most cases, you can fine-tune solver behavior using setOptionValue.

An LP model that is neither infeasible nor unbounded has an optimal solution at a vertex of the feasible region. This is known as a basic solution.

• Basis: A partition of decision variables (including slack variables) into basic variables (as many as there are constraints) and nonbasic variables.
• Nonbasic variables: Their values are equal to their lower or upper bounds.
• Degeneracy: A situation where a basic variable's value is equal to its lower or upper bound.

Hot Starting

When an LP model is modified slightly, the simplex solver can use the optimal basis of the original LP to solve the new one efficiently. This is called hot starting. If modifications are significant, it may be more efficient to solve from scratch using the IPM (Interior Point Method) solver.