Assume that we have solved a (standard) linear program $$ \text{minimize}_{x\in {\mathbb R^n}}\,\, c_0^Tx, \,\,\,\,\, \text{s.t. } A_0x \leq b_0, $$ and would like to know how sensitive is the optimal objective value to the fluctuations in $c_0$, $A_0$, $b_0$. For this, we introduce parameterised linear program $$ V(t) = \text{minimize}_{x\in {\mathbb R^n}}\,\, c(t)^Tx, \,\,\,\,\, \text{s.t. } A(t)x \leq b(t), $$ where $c(t)=c_0+tc_1$, $A(t)=A_0+tA_1$, $b(t)=b_0+tb_1$, $t\in[0,1]$ is a parameter, and would like to estimate the right derivative $V(0+)$. A naive approach would be to solve the problem for $t=0$, then for some small $t=\epsilon>0$, and approximate $V(0+)\approx \frac{V(\epsilon)-V(0)}{\epsilon}$. This would require solving the problem twice, and the choice of $\epsilon$ is unclear.
There is a Theorem providing (under some compactness conditions) a direct formula for $V(0+)$ $$ V(0+) = \inf\limits_{x\in X^*(0)} \sup\limits_{\lambda \in \Lambda^*(0)} L_t(x,\lambda,0), $$ where $L_t(x,\lambda,0)$ is the partial derivative in $t$ of the Lagrangian $L(x,\lambda,t)$ at $t=0$, $X^*(0)$ and $\Lambda^*(0)$ are the sets of optimal solutions to the primal and dual problems with $t=0$, respectively. The results of this type are known as Envelope theorems in economic literature, and sensitivity analysis (or perturbation analysis) in mathematics.
If primal and dual problems have unique solutions $x^*$ and $\lambda^*$ respectively, this simplifies to $$ V(0+) = L_t(x^*,\lambda^*,0), $$ and can be used to actually compute $V(0+)$. However, in general $X^*(0)$ is not a singleton, and standard methods like simplex return some $x\in X^*(0)$, but not describe the whole solution set.
So, the question is: can this formula, or any other theoretical result, be used to actually compute $V(0+)$ for practical problems (with hundreds or thousands variables and constraints), with performance better than (or at least comparable to) the naive approach?
