The LP Procedure

Sensitivity Analysis

Subsections:

Sensitivity analysis is a technique for examining the effects of changes in model parameters on the optimal solution. The analysis enables you to examine the size of a perturbation to the right-hand-side or objective vector by an arbitrary change vector for which the basis of the current optimal solution remains optimal.

Note: When sensitivity analysis is performed on integer-constrained problems, the integer variables are fixed at the value they obtained in the integer optimal solution. Therefore, care must be used when interpreting the results of such analyses. Care must also be taken when preprocessing is enabled, because preprocessing usually alters the original formulation.

Right-Hand-Side Sensitivity Analysis

Consider the problem $(lpr(\phi ))$:

\[ \begin{array}{ll} x^{opt}(\phi )= & \min c^ Tx \\ \mr{subject\ to} \quad & A x \, \{ \geq , =, \leq \} \, b + \phi r \\ & \ell \leq x \leq u \\ \end{array} \]

where r is a right-hand-side change vector.

Let $x^{opt}(\phi )$ denote an optimal basic feasible solution to $(lpr(\phi ))$. PROC LP can be used to examine the effects of changes in $\phi $ on the solution $ x^{opt}(0)$ of problem $ (lpr(0))$ . For the basic solution $ x^{opt}(0)$, let B be the matrix composed of the basic columns of A and let N be the matrix composed of the nonbasic columns of A. For the basis matrix B, the basic components of $ x^{opt}(0)$, written as $ x^{opt}(0)_ B$, can be expressed as

\[ x^{opt}(0)_ B = B^{-1} (b-Nx^{opt}(0)_ N) \]

Furthermore, because $ x^{opt}(0)$ is feasible,

\[ \ell _ B\leq B^{-1}(b-Nx^{opt}(0)_ N)\leq u_ B \]

where $ \ell _ B$ is a column vector of the lower bounds on the structural basic variables, and $ u_ B$ is a column vector of the upper bounds on the structural basic variables. For each right-hand-side change vector r identified in the RHSSEN statement, PROC LP finds an interval $[\phi _{min} ,\phi _{max}]$ such that

\[ \ell _ B\leq B^{-1}(b+\phi r-Nx^{opt}(0)_ N)\leq u_ B \]

for $\phi \in [\phi _{min} ,\phi _{max}]$. Furthermore, because changes in the right-hand side do not affect the reduced costs, for $\phi \in [\phi _{min} ,\phi _{max}],$

\[ x^{opt}(\phi )^ T=((B^{-1}(b+\phi r-Nx^{opt}(0)_ N))^ T,x^{opt}(0)_ N^ T) \]

is optimal in $(lpr (\phi ))$.

For $\phi =\phi _{min}$ and $\phi =\phi _{max}$, PROC LP reports the following:

  • the names of the leaving variables

  • the value of the optimal objective in the modified problems

  • the RHS values in the modified problems

  • the solution status, reduced costs and activities in the modified problems

The leaving variable identifies the basic variable $ x_ i$ that first reaches either the lower bound $ \ell _ i$ or the upper bound $ u_ i$ as $\phi $ reaches $\phi _{min}$ or $\phi _{max}$. This is the basic variable that would leave the basis to maintain primal feasibility. Multiple RHSSEN variables can appear in a problem data set.

Price Sensitivity Analysis

Consider the problem $(lpp(\phi ))$:

\[ \begin{array}{ll} x^{opt}(\phi )= & \min (c+\phi r)^ Tx \\ \mr{subject\ to} \quad & A x \, \{ \geq , =, \leq \} \, b \\ & \ell \leq x \leq u \\ \end{array} \]

where r is a price change vector.

Let $x^{opt}(\phi )$ denote an optimal basic feasible solution to $(lpp (\phi ))$. PROC LP can be used to examine the effects of changes in $\phi $ on the solution $ x^{opt}(0)$ of problem $ (lpp(0))$. For the basic solution $ x^{opt}(0)$, let B be the matrix composed of the basic columns of A and let N be the matrix composed of the nonbasic columns of A. For basis matrix B, the reduced cost associated with the ith variable can be written as

\[ rc_ i(\phi )=((c+\phi r)^ T_ N- (c+\phi r)^ T_ BB^{-1}N)_ i \]

where $(c +\phi r )_ N$ and $(c +\phi r)_ B$ is a partition of the vector of price coefficients into nonbasic and basic components. Because $ x^{opt}(0)$ is optimal in $ (lpp(0))$, the reduced costs satisfy

\[ rc_ i(\phi )\geq 0 \]

if the nonbasic variable in column i is at its lower bound, and

\[ rc_ i(\phi )\leq 0 \]

if the nonbasic variable in column i is at its upper bound.

For each price coefficient change vector r identified with the keyword PRICESEN in the TYPE variable, PROC LP finds an interval $[\phi _{min} ,\phi _{max}]$ such that for $\phi \in [\phi _{min} ,\phi _{max}]$,

\[ rc_ i(\phi )\geq 0 \]

if the nonbasic variable in column i is at its lower bound, and

\[ rc_ i(\phi )\leq 0 \]

if the nonbasic variable in column i is at its upper bound. Because changes in the price coefficients do not affect feasibility, for $\phi \in [\phi _{min} ,\phi _{max}]$, $x^{opt}(\phi )$ is optimal in $(lpp(\phi ))$. For $\phi =\phi _{min}$ and $\phi =\phi _{max}$, PROC LP reports the following:

  • the names of entering variables

  • the value of the optimal objective in the modified problems

  • the price coefficients in the modified problems

  • the solution status, reduced costs, and activities in the modified problems

The entering variable identifies the variable whose reduced cost first goes to zero as $\phi $ reaches $\phi _{min}$ or $\phi _{max}$. This is the nonbasic variable that would enter the basis to maintain optimality (dual feasibility). Multiple PRICESEN variables may appear in a problem data set.