A Linear Program in n variables x1, ..., xn with m constraints of the form ∑j=1n ajxj ≤ c (the relations in any of the constraints may also be = or ≥) may be represented in matrix form as:
pmatrix(a11 & ... & a1n
vdots & ddots & vdots
am1 & ... & amn
).
pmatrix(x1
vdots
xn
)
pmatrix(REL)
pmatrix(c1
vdots
cn
)
where pmatrix(REL) represents a componentwise relation between vectors, with each element =, ≤, or ≥.
Note that there is an additional implicit constraint, wherein all variables are assumed to be nonnegative.
We wish to find a solution pmatrix(xi) that maximises (or minimises) the objective function: ∑i = 1n oi xi
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:
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 [Naz87], [Chv83], [OH68] and [NW88].