Resource which explain different stochastic method with some intuition

Question

Hope my question fit this community. I have taken Stochastic Optimization course (2 credits). The course content are:

• Deterministic VS Stochastic Linear Program
• Two-Stage Recourse Problem
• Multi-Stage Recourse Problem
• Chance Constrained SP
• Stochastic Integer Program

This week I had taught Two-Stage Recourse Problem but couldn't manage to understand the context like why this method works? Specially, inequality like $\text{EV}\geq\text{WS}\geq\text{RP}\geq\text{EEV}$ where EV, WS, RP and EEV stand for Expected Value problem, Wait and See problem, Recourse Problem and Expected value of Expected value problem respectively. And indexes like EVPI (Expected Value of Perfect Information) and VSS (Value of Stochastic Solution). All of these seem are memorizing things without understanding what's going on under the hood. Currently, my Professor follows "Introduction to Stochastic Programming" by Birge and Louveaux.

Is there any Book/Resource which design those things in a deeper fashion for completely beginner people?

---

@PenghuiGuo add some citations, which is great. I have cleared some of my doubts on EV, EEV and WS. But still couldn't manage to understand the RP intuitively. Even the method seems confusing because sometimes, Deterministic equivalent of SP problem directly, without decomposition (considering every scenario variables in a single linear programming) was called as RP and sometimes, they split the non-stochastic parameters and solve $Q(x,\xi)$ seperately. $$\begin{array}{ll}\min & c^{T} x+E_{\xi}[Q(x, \xi)] \qquad\text{1st stage}\\ \text { s.t. } \quad & A x \leq b \\ & x \geq 0 \\ &Q(x, \xi)=\min q^{T} y \qquad\text{2nd stage}\\ \text { s.t. } \quad & T x+W y \leq h \\ & y \geq 0\end{array}$$

Answer 1

Since in the question you state $EV \geq WS \geq {\bf RP} \geq EEV$, following we assume a maximization problem.

We start from the Recourse Problem (RP) as it is exactly the stochastic programming problem, no matter how it is formulated (the formulation in the question or the extensive form, which is also known as deterministic equivalent). The motivation of the extensive form is that the formulation with a value function $Q(x, \xi)$ can not be solved with known technics in the deterministic optimization. But the extensive form is nothing but a Linear Programming that can be solved with what we have know in the deterministic optimization, e.g. the simplex method. However, the extensive form can be difficult to solve, since it has more variables than the form in the question. This ask for technics like the Benders Decomposition, which is not going to be detailed in this question.

The stochastic programming has both here-and-now decisions (first-stage) and wait-and-see decisions (second-stage). What complicating the stochastic programming is the first-stage decision is made before the second-stage information is known, and the first-stage decision has to be constant for all the second-stage information reveal. If we remove this requirement (constraint), independent problems will be got, i.e., the wait-and-see problem (WS). Since some constraints are removed from the RP in WS, the solution yield by WS should not be worse than that of RP. $WS \geq RP$ is thus be explained.

The Expected Value of Expected Value Problem (EEV) is yield by fixing the first-stage variables to the solution of the Expected Value Problem, which is not necessarily optimal for the original RP. Alternatively, the Expected Value Problem solution can be replaced with the worst case problem solution or heuristics solution, which is also not optimal for RP. Hence, $RP \geq EEV$.

I doubt that the Expected Value Problem (EV) has better objective value than the RP. See [1] page 33.

[1] Moraza, S.L., 2015. Two-Stage Stochastic Optimization. An Application in the Third Sector. https://addi.ehu.es/bitstream/handle/10810/18673/TFG_S.Laconcepcion.pdf?sequence=1

---

The original paper for Value of Stochastic Solution (VSS):

• Birge, J.R., 1982. The value of the stochastic solution in stochastic linear programs with fixed recourse. Mathematical Programming 24, 314–325. https://doi.org/10.1007/BF01585113

The original paper for Expected Value of Perfect Information (EVPI):

• Raiffa, H., & Schlaifer, R. (1961). Applied Statistical Decision Theory. (1st ed.). Boston: Harvard University Press.

You may also refer to:

• Madansky, A., 1960. Inequalities for Stochastic Linear Programming Problems. Management Science 6, 197–204. https://doi.org/10.1287/mnsc.6.2.197

And an example:

• Linderoth, J., 2016. Stochastic Programming Modeling. https://www.ima.umn.edu/2015-2016/ND8.1-12.16/25379