The LP Procedure

Parametric Programming

Subsections:

Right-Hand-Side Parametric Programming
Price Parametric Programming

Sensitivity analysis and range analysis examine how the optimal solution behaves with respect to perturbations of model parameter values. These approaches assume that the basis at optimality is not allowed to change. When greater flexibility is desired and a change of basis is acceptable, parametric programming can be used.

As with the sensitivity analysis case, care must be used in interpreting the results of parametric programming when the problem has integers or the preprocessing option is enabled.

Right-Hand-Side Parametric Programming

As discussed in the section Right-Hand-Side Sensitivity Analysis, for each right-hand-side change vector $r$ , PROC LP finds an interval $[\phi _{min} ,\phi _{max}]$ such that 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 the fixed basis $B$ . Leaving variables that inhibit further changes in $\phi$ without a change in the basis $B$ are associated with the quantities $\phi _{min}$ and $\phi _{max}$ . By specifying RHSPHI= $\Phi$ in either the PROC LP statement or the RESET statement, you can examine the solution $x^{opt}(\phi )$ as $\phi$ increases or decreases from 0 to $\Phi$ .

When RHSPHI= $\Phi$ is specified, the procedure first finds the interval $[\phi _{min} ,\phi _{max}]$ as described previously. Then, if $\Phi \in [\phi _{min} ,\phi _{max}]$ , no further investigation is needed. However, if $\Phi >\phi _{max}$ or $\Phi <\phi _{min}$ , then the procedure attempts to solve the new problem $(lpr(\Phi ))$ . To accomplish this, it pivots the leaving variable out of the basis while maintaining dual feasibility. If this new solution is primal feasible in $(lpr(\Phi ))$ , no further investigation is needed; otherwise, the procedure identifies the new leaving variable and pivots it out of the basis, again maintaining dual feasibility. Dual pivoting continues in this manner until a solution that is primal feasible in $(lpr(\Phi ))$ is identified. Because dual feasibility is maintained at each pivot, the $(lpr(\Phi ))$ primal feasible solution is optimal.

At each pivot, the procedure reports on the variables that enter and leave the basis, the current range of $\phi$ , and the objective value. When $x^{opt}(\Phi )$ is found, it is displayed. If you want the solution $x^{opt}(\phi )$ at each pivot, then specify the PARAPRINT option in either the PROC LP or the RESET statement.

Price Parametric Programming

As discussed in the section Price Sensitivity Analysis, for each price change vector $r$ , PROC LP finds an interval $[\phi _{min},\phi _{max}]$ such that for each $\phi \in [\phi _{min}, \phi _{max}]$ ,

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

satisfies the conditions for optimality in $(lpp(\phi ))$ for the fixed basis $B$ . Entering variables that inhibit further changes in $\phi$ without a change in the basis $B$ are associated with the quantities $\phi _{min}$ and $\phi _{max}$ . By specifying PRICEPHI= $\Phi$ in either the PROC LP statement or the RESET statement, you can examine the solution $x^{opt}(\phi )$ as $\phi$ increases or decreases from 0 to $\Phi$ .

When PRICEPHI= $\Phi$ is specified, the procedure first finds the interval $[\phi _{min} ,\phi _{max}]$ , as described previously. Then, if $\Phi \in [\phi _{min} ,\phi _{max}]$ , no further investigation is needed. However, if $\Phi >\phi _{max}$ or $\Phi <\phi _{min}$ , the procedure attempts to solve the new problem $(lpp(\Phi ))$ . To accomplish this, it pivots the entering variable into the basis while maintaining primal feasibility. If this new solution is dual feasible in $(lpp(\Phi ))$ , no further investigation is needed; otherwise, the procedure identifies the new entering variable and pivots it into the basis, again maintaining primal feasibility. Pivoting continues in this manner until a solution that is dual feasible in $(lpp(\Phi ))$ is identified. Because primal feasibility is maintained at each pivot, the $(lpp(\Phi ))$ dual feasible solution is optimal.