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, provided by the lp_solve library. The codes are:

0

Optimal Solution

1

Failure

2

Infeasible problem

3

Unbounded problem

4

Failure

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 written by Michel Berkelaar (michel@ics.ele.tue.nl). The library source may be found at ftp://ftp.ics.ele.tue.nl/pub/lp_solve/.

For further reference see [Nazareth, 1987], [Chvatal, 1983], [Orchard–Hays, 1968] and [Nemhauser and Wolsey, 1988].