The LP subroutine solves the linear programming problem.

The input arguments to the LP subroutine are as follows:

a

is an vector that specifies the technological coefficients, where is less than or equal to .

b

is an vector that specifies the right-side vector.

cntl

is an optional row vector with 1 to 5 elements. If CNTL=(indx, nprimal, ndual, epsilon, infinity), then

indx

is the subscript of nonzero objective coefficient.

nprimal

is the maximum number of primal iterations.

ndual

is the maximum number of dual iterations.

epsilon

is the value of virtual zero.

infinity

is the value of virtual infinity.

The default values are as follows: indx equals , nprimal equals 999999, ndual equals 999999, epsilon equals 1.0E8, and infinity is machine dependent. If you specify ndual or nprimal or both, then on return they contain the number of iterations actually performed.

u

is an optional array of dimension that specifies upper bounds on the decision variables. If you do not specify , the upper bounds are assumed to be infinity.

l

is an optional array of dimension that specifies lower bounds on the decision variables. If is not given, then the lower bounds are assumed to be 0 for all the decision variables. This includes the decision variable associated with the objective value, which is specified by the value of indx.

basis

is an optional array of dimension that specifies the current basis. This is given by identifying which columns are explicitly in the basis and which columns are at their upper bound, as given in . The absolute value of the elements in this vector is a permutation of the column indices. The columns specified in the first elements of basis are considered the explicit basis. The absolute value of the last elements of basis are the indices of the nonbasic variables. Any of the last elements of basis that are negative indicate that the corresponding nonbasic variable is at its upper bound. On return from the LP subroutine, the basis vector contains the final basis encountered. If you do not specify basis, then the subroutine assumes that an initial basis is in the last columns of and that no nonbasic variables are at their upper bound.

rc

returns one of the following scalar return codes:

0

solution is optimal

1

solution is primal infeasible and dual feasible

2

solution is dual infeasible and primal feasible

3

solution is neither primal nor dual feasible

4

singular basis encountered

5

solution is numerically unstable

6

subroutine could not obtain enough memory

7

number of iterations exceeded

x

returns the current primal solution in a column vector of length .

dual

returns the current dual solution in a row vector of length .

The LP subroutine solves the linear program:

The subroutine first inverts the initial basis. If the basis vector is given, then the initial basis is the submatrix identified by the first elements in basis; otherwise, the initial basis is defined by the last columns of . If the initial basis is singular, the subroutine returns with RC=4. If the basis is nonsingular, then the current dual and primal solutions are evaluated. If neither is feasible, then the subroutine returns with RC=3. If the primal solution is feasible, then the primal algorithm iterates until either a dual feasible solution is encountered or the number of NPRIMAL iterations is exceeded. If the dual solution is feasible, then the dual algorithm iterates until either a primal feasible solution is encountered or the number of NDUAL iterations is exceeded. When a basis is identified that is both primal and dual feasible, then the subroutine returns with RC=0.

Note that care must be taken when solving a sequence of linear programs that use the NPRIMAL or NDUAL control parameters. Because the LP subroutine resets the NPRIMAL and NDUAL parameters to reflect the number of iterations executed, subsequent invocations of the LP subroutine will have the number of iterations limited to the number used by the last LP subroutine executed. In these cases you should consider resetting these parameters prior to each LP call.

Consider the following example to maximize subject to the constraints , and , and . The problem is solved by using the following statements:

/* the problem data */
obj = {1 0};
coef = {1 1};
b = {0, 10};

/* embed the objective function in the coefficient matrix */
a = obj // coef;
a = a || {-1, 0};

/* solve the problem */
call lp(rc, x, dual, a, b);
print rc, x, dual;