Language Reference: LP Call :: SAS/IML(R) 9.2 User's Guide

Language Reference

LP Call

solves the linear programming problem

CALL LP( rc, , dual, , $b\lt$ , cntl<, u<, l<, basis>);

The inputs to the LP subroutine are as follows:

is an

vector specifying the technological coefficients, where

is less than or equal to

is an

vector specifying 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.0E-8, and infinity is machine dependent. If you specify ndual or nprimal or both, then on return they contain the number of iterations actually performed.

is an optional array of dimension

specifying upper bounds on the decision variables. If you do not specify

, the upper bounds are assumed to be infinity.

is an optional array of dimension

specifying 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

specifying 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

: 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:

$& & \max (0, ... ,0,1,0, ... ,0) x \ & & {st. } {ax} = b \ & & l \leq x \leq u$

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 and using the NPRIMAL or NDUAL control parameters or both. 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 $x_1 + x_2 \leq 10$ and $x_1 \geq 0$ . The problem is solved by using the following code:

  
       /* 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);

The result is as follows:

  
                 RC            1 row       1 col     (numeric) 
  
                                           0 
  
  
                 X             3 rows      1 col     (numeric) 
  
                                          10 
                                           0 
                                          10 
  
  
                 DUAL          1 row       2 cols    (numeric) 
  
                                     -1         1

Top of Page