2
$\begingroup$

TLDR: When doing sensitivity analysis (specifically the objective coefficients), there maximum allowable increase and decrease before the solution changes is only valid when a single coefficient changes. Is there a way to generalize when multiple values change?

Context: My model (see below) is a simple minimize cost of a weighted sum subject to 2 constraints. The coefficients in my objective are not known well and vary based on some distribution. So I approximate by using the sample mean. So i sample multiple times to get the coefficients subject to some confidence interval. The more I sample, the tighter the interval but each sample is VERY VERY computationally expensive. The cardinality of i and j is at most 6, giving us a maximum of 36 variables. So, I wanted to see if there is stage where given the confidence intervals, I know that the LP solution is unlikely change with additional samples?

My mind first went to sensitivity analysis but the results are only valid when a single parameter changes. But since this is a small problem, is there a way to generalize this further?

enter image description here

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

For either changes to the objective or changes to the right hand side values, the sensitivity results hold for multiple changes as long as the sum of the fraction of the allowed change used by each parameter does not exceed 1. Say the maximum increase for $\overline{d^{(1)}}$ is $D_1$ and you increase it by $d_1 \in [0,D_1],$ and the maximum decrease for $\overline{d^{(2)}}$ is $D_2 > 0$ and you decrease it by $d_2\in[0, D_2].$ If $$\frac{d_1}{D_1} + \frac{d_2}{D_2} \le 1,$$ the shadow prices/dual values remain the same. This is conservative, in the sense that if you make bigger changes the shadow prices might stay the same (but very well might change). You can apply the same logic to changes to objective coefficients.

Improve this answer
$\endgroup$
3
  • 3
    $\begingroup$ glossary.informs.org/ver2/mpgwiki/index.php?title=100%25_Rule $\endgroup$
    – RobPratt
    Commented May 25, 2023 at 15:29
  • $\begingroup$ Thanks! The following question is more out of curiosity. In OR, there is always someone who tries to push this limit further. Has anyone proved a non-conservative limit to this change and the necessary conditions for that? $\endgroup$
    – Abilash
    Commented May 25, 2023 at 19:11
  • $\begingroup$ I'm not aware of anything meaningful. Let's say your primal problem is min (with RHS $b$) and thus the dual is max. The objective coefficient vector of the dual is $b.$ For small changes in $b,$ the optimal dual solution remains the same and so the objective change is exactly the inner product of the dual solution $y*$ and the changes to $b.$ For larger changes to $b,$ $y*$ remains feasible, so the dual changes by at least that inner product, but the optimal solution of the dual may jump to some other corner of the dual feasible region. That corner could be pretty much anywhere. $\endgroup$
    – prubin ♦
    Commented May 25, 2023 at 20:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.