1
$\begingroup$

I have the following 2 stage Stochastic Programming program:

\begin{align}\min_x& \quad x+\sum_{s=1}^{3}p_sQ_s(x)\\\text{s.t.}&\quad x\in\Bbb R\\&\quad Q_s(x)=\min\left[\begin{pmatrix}1&6&−2\end{pmatrix}y_s\right]\\&\quad\text{s.t.}\quad\begin{pmatrix}2 & 0 &0 &\\1 &0 &−4\end{pmatrix}y_s=b_s−\begin{pmatrix}−2\\ 1\end{pmatrix}x\\&\qquad\qquad y_s\ge0,y_s\in\Bbb R^3.\end{align}

where $b_1=\begin{pmatrix}1 \\0 \end{pmatrix},b_2=\begin{pmatrix}0 \\ 1\end{pmatrix},b_3=\begin{pmatrix}−1 \\1\end{pmatrix}$ and $p_1=p_2=p_3=1/3$.

How do I find the extreme rays and points in order to do Benders Decomposition? I really appreciate the help I can get! Thank you :)

$\endgroup$
5
  • $\begingroup$ Are you solving the problem numerically (generating the Benders cuts by solving each LP subproblem numerically), or are you asking how to find a closed-form solution to the whole thing? $\endgroup$ – prubin Apr 25 '20 at 22:24
  • $\begingroup$ @prubin solving it numerically $\endgroup$ – Anon Apr 25 '20 at 22:24
  • $\begingroup$ Are you sure the formulation above is correct? It can be solved in closed form, without using Benders decomposition (or even linear programming). $\endgroup$ – prubin Apr 26 '20 at 22:14
  • $\begingroup$ @prubin yes, I'm sure that the problem is correct. I know that for the scenario s=3 the solution of the problem is infeasible, and when s=1 it is feasible.. Just not sure on how to get the extreme ray vector.. $\endgroup$ – Anon Apr 26 '20 at 22:18
  • $\begingroup$ Scenario 3 is not necessarily infeasible; it depends on $x$. Set $x=1$. The right side of the scenario 3 subproblem is $(-1, 1)'-(-2, 1)'\cdot 1=(1, 0)'$. $y=(1/2, 0, 1/8)\ge 0$ solves the subproblem. $\endgroup$ – prubin Apr 27 '20 at 22:25

Your Answer

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

Browse other questions tagged or ask your own question.