Introduction

A Linear Program in \(n\) variables \(x_1, \cdots, x_n\) with \(m\) constraints of the form \(\sum_{j=1}^n a_jx_j~\le~c\) (the relations in any of the constraints may also be \(=\) or \(\ge\)) may be represented in matrix form as:

\[\begin{split}\begin{pmatrix}a_{11} & \cdots & a_{1n}\\ \vdots & \ddots & \vdots\\ a_{m1} & \cdots & a_{mn}\end{pmatrix}\;. \begin{pmatrix}x_1\\ \vdots\\ x_n\end{pmatrix}\; \quad \begin{pmatrix}REL\end{pmatrix} \quad \begin{pmatrix}c_1\\ \vdots\\ c_n\end{pmatrix}\;\end{split}\]

where \(\begin{pmatrix}REL\end{pmatrix}\) represents a componentwise relation between vectors, with each element \(=\), \(\le\), or \(\ge\).

Note that there is an additional implicit constraint, wherein all variables are assumed to be nonnegative.

We wish to find a solution \(\begin{pmatrix}x_i\end{pmatrix}\;\) that maximises (or minimises) the objective function: \(\sum_{i = 1}^n o_i x_i\)

Magma provides two methods for solving LP problems. The first is to set up suitable constraint matrices and then use an explicit LP solving function to solve the problem. The second involves creating an instance of the LP process, which is of category LP. Constraints are added and options set before calling Solution to get a solution to the problem.

All functions that actually solve an LP problem return a solution vector together with an integer code representing the state of the solution. The code is lp_solve’s own return value, passed through unchanged.

0

OPTIMAL – an optimal solution was found

2

INFEASIBLE – the problem is infeasible

3

UNBOUNDED – the problem is unbounded

4

DEGENERATE – the simplex stalled, and no recovery strategy was left to try

5

NUMFAILURE – numerical failure in the solver

25

ACCURACYERROR – the solution failed the solver’s final accuracy check

The other codes lp_solve defines cover conditions Magma does not configure the solver to produce, such as a time limit, a user abort, a search stopped at a breakpoint, or a model disposed of by presolve. They are listed with the return values of solve in the lp_solve reference guide at https://lp-solve.github.io/solve.htm.

Magma supports LP problems over Integer, Rational, and Real rings. For Integer and Real problems, the solutions will be provided as Integer and Real vectors respectively. For LP problems provided in Rationals, the solution is a Real vector.

Linear programming in Magma is implemented using the lp_solve library, originally written by Michel Berkelaar and now maintained as lp_solve 5.5. The library source may be found at https://github.com/lp-solve/lp_solve, and its reference guide at https://lp-solve.github.io/.

For further reference see [Naz87], [Chv83], [OH68], and [NW88].