4
$\begingroup$

Assuming that we have a linear math model with $N$ bounded $[0,1]$ uncertain parameters $p_n$ within a typical polyhedral budget uncertainty set that says $\sum_{n}{p_n} \le \Gamma$.

I want to find which uncertain parameters are activated in the robustly optimal solution. If $\Gamma = 0$, I know that none of the parameters were activated, so I recover the nominal solution. For $\Gamma > 0$, a robustly optimal solution will guarantee the feasibility of the solution if up to $\Gamma$ uncertain parameters go to their worst case.

The question is which of the parameters were activated?

$\endgroup$
3
$\begingroup$

A robust optimal solution has to satisfy all constraints for each choice of the uncertainty parameters. Thus you might not be able to point out one particular set that is active for an optimal solution. Consider the following small problem:

\begin{align} \min x_1+x_2+x_3\\ x_1+x_2&\geq b_3 \\ x_1+x_3&\geq b_2 \\ x_2+x_3&\geq b_1 \\ x_1, x_2, x_3&\geq0 \\ \forall b_1, b_2, b_3 \geq0 &\text{ s.t. } b_1+b_2+b_3 \leq 1. \end{align}

Here $b_1, b_2, b_3$ are the uncertainty parameters and $\Gamma=1$.

The optimal solution is $x_1=x_2=x_3=\frac{1}{2}$, as the solution has to hold for each choice of $b_i$. Also one can see that one can not name exactly one ($\Gamma$) of the variables that are responsible for this solution, as each of the three constraints is tight for a different choice of $b_i=1$.

I hope this helps with the intuition.

$\endgroup$
3
  • $\begingroup$ While the intuition helps, it is not a solution to the problem. Probably the solution is a MIP that tries to maximize the number of parameters that reach their worst case for a given robust x*. Then a set of additional optimizations with appended integer cuts, to identify all of the possible sets of solutions. $\endgroup$ – user4168715 Feb 19 at 15:06
  • 1
    $\begingroup$ I am pretty sure if you want to identify ALL the worst case sets it's gonna be exponentially many in general. $\endgroup$ – SimonT Feb 19 at 21:02
  • 1
    $\begingroup$ Maybe a more intersting question would be to identify whether a certain parameter is contained in any of the worst case sets - some kind of critical parameter. I think this could be tested by scaling each of the parameters down by some $(1-\epsilon)$ to see whether the solution gets worse. $\endgroup$ – SimonT Feb 19 at 21:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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