How does the solution of our optimization model react to small perturbations of the input data?
Don't worry, we are not going to review the principles of the sensitivity analysis, one can refer for instance to [1], but we will show that the commonly used techniques can hide unexpected pitfalls.
In general, an LP sensitivity analyzer returns the shadow price of a given input parameter, i.e. broadly speaking the rate of variation of the objective function with respect to the parameter, and the interval in which the that price is constant.
Every OR practitioner should know this tool and its potential pitfalls. But it is not often the case...
here goes the story: one of our customer was puzzled by the results of the sensitivity analysis he was carrying on some LP problems (related to some kind of unit commitment problem): why the shadow prices of the solutions were sometimes different? And why they did not seem to make much sense to him?
He boiled down to a VERY minimal example for us:
\begin{equation}
\begin{aligned}
& \min & 10^5 x_1 + x_2 \\
\\
&& x_1 + x_2 =100\\
\\
&& x_1,x_2 \in [0,100]
\end{aligned}
\end{equation}
The problem is so simple that can be solved by hand: the optimal solution is $(x_1^\star, x_2^\star)=(0,100)$. It is also degenerate (either the upper or the lower bounds can be dropped) with multiple optimal basis: to see that, let's recast the problem in standard form:
\begin{equation}
\begin{aligned}
& \min & 10^5 x_1 + x_2 \\
\\
&& x_1 + x_2 =100\\
&& x_1 + s_1 =100\\
&& x_2 + s_2 =100\\
\\
&& x_1,x_2,s_1,s_2 \geq 0
\end{aligned}
\end{equation}
The optimal solution now reads $(x_1^\star, x_2^\star, s_1^\star, s_2^\star )=(0,100,100,0)$. It is straightforward to see that there are two optimal basis: $B_1=\{x_2,s_1,s_2\}$ and $B_2=\{x_2,s_1,x_1\}$.
What if we ask for a sensitivity analysis about the linear constraint in problem (1)? Using the command line MOSEK sensitivity analyser the answer is:
BOUNDS CONSTRAINTS
INDEX NAME BOUND LEFTRANGE RIGHTRANGE LEFTSHADOW RIGHTSHADOW
0 c0000 FX -1.000000e+02 -0.000000e+00 1.000000e+00 1.000000e+00
that is the RHS can be reduced by up to $100$ (the LEFTRANGE) with unitary shadow price. But we have no information about what might happen if we increase the RHS. Let's visualize what we would like to investigate (RHS is renamed as $\beta$):
The gray area represent the region defined by the box constraints. The red line is the feasible region of problem (1) and the optimal value is the red dot on the left-up corner. Varying RHS results in a translation of that feasible region and a different optimal value. The yellow lines/points correspond to the feasible region/optimal solution as RHS decreases; the light-blue ones, corresponding to an increase of RHS, are not reported by the analyzer. But still, it is clearly possible to increase RHS...so what's going on?
This problem is quite well-known in the OR community. In [3], the main issues and pitfall are clearly summarized: the standard analysis, named Type-I, depends on the optimal basis. If more than one basis corresponds to an optimal solution, the analysis will be in general incomplete because limited by the changing of basis.
In our case, the solutions obtained decreasing RHS share the same basis, while a different basis corresponds to the other ones. So the scope of our analysis is limited by the basis reported by the solver.
A more accurate analysis can be carried out using more computational intensive techniques, sometimes referred as Type-III sensitivity or Optimal Partition Sensitivity (OPS): simply speaking, a sequence of LP problems based on the current optimal solution are solved in order to asses the sensitivity, regardless of the particular basis that might correspond to the solution (see [2]).
Again, let's look at our example. We use the OPS tool available in MOSEK to analyze again the same constraint. The result follows:
BOUNDS CONSTRAINTS
INDEX NAME BOUND LEFTRANGE RIGHTRANGE LEFTSHADOW RIGHTSHADOW
0 c0000 FX -1.000000e+02 1.000000e+02 1.000000e+00 1.000000e+05
Now we can investigate also the increasing of the RHS! As one might expect, a different shadow price correspond to this side of the RHS interval.
The lesson is that in most of the practical applications, optimal solutions are degenerate and thus the Type-I sensitivity analysis might be incomplete. In general, there is no way to predict which basis will be returned by a solver. The OPS analysis, despite being more computational demanding, can deliver more accurate information and it is therefore a tool that practitioners should consider and learn.
[1] Chvátal, V. (1983). Linear programming.
[2] Roos C., Terlaky T., Vial J. P. (1997). Theory and algorithms for linear optimization: an interior point approach. Chichester: Wiley.
[3] Koltai T., Terlaky T. (2000). The difference between the managerial and mathematical interpretation of sensitivity analysis results in linear programming. International Journal of Production Economics, 65(3), 257-274.
