The INTPOINT Procedure

Mathematical Description of LP

A linear programming (LP) problem has a linear objective function and a collection of linear constraints. PROC INTPOINT finds the values of variables that minimize the total cost of the solution. The value of each variable is on or between the variable’s lower and upper bounds, and the constraints are satisfied.

If an LP has g variables and k constraints, then the formal statement of the problem solved by PROC INTPOINT is

\[ \begin{array}{ll} \mr{minimize} & d^ T z \\ \mr{subject\ to} & Q z \, \{ \geq , =, \leq \} \, r \\ & m \leq z \leq v \\ \end{array} \]

where

  • d is the $ g \times 1$ variable objective function coefficient vector

  • z is the $ g \times 1$ variable value vector

  • Q is the $ k \times g$ constraint coefficient matrix for the variables, where $ Q_{i,j}$ is the coefficient of variable j in the ith constraint

  • r is the $ k \times 1$ side constraint right-hand-side vector

  • m is the $ g \times 1$ variable lower bound vector

  • v is the $ g \times 1$ variable upper bound vector