Stochastic dual dynamic programming (SDDP) algorithm solves stage-wise optimization problem through sampling scenarios. In this regard, it is obvious to see that wait-and-see uncertainty can be easily handled by SDDP (first sample random noise at each decision node in a scenario and solve a deterministic problem). On the other hand, is it possible to solve a multi stage optimization problem with here-and-now uncertainty nodes (random noise at a particular node is realized after respective stage specific problem is solved)? In this case, stage specific problems can not be made deterministic by simply sampling random noise at the respective stages.
$\begingroup$
$\endgroup$
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
8
Here-and-now uncertainty problems, which are also known as Decision-Hazard problems, are problems that decisions need to be made before the revelation of uncertain parameters on each node of a scenario tree. In multi-stage stochastic programming, nonanticaptivity constraints are required. That is, no matter what the revealed uncertain data is in stage $t$, decisions in stage $t-1$ should be consistent. This is ensured by SDDP automatically, which implies the first method to handle Decision-Hazard problems:
- Add auxiliary variables to the parent node (denote as $p$) of Decision-Hazard node (denote as $n$). Then add constraints to $n$ to make decisions of $n$ the same as that of $p$. In other words, all the Decision-Hazard types of decisions are made in the previous stage.
There is also another way:
- Treat Decision-Hazard subproblems in SDDP as two-stage stochastic problems, in which the decisions that need to be made before the revelation of uncertain parameters are the first-stage decisions, while the other decisions are the second-stage decisions.
Some related papers that may be helpful:
- Dowson, O. (2020). The policy graph decomposition of multistage stochastic programming problems. Networks, 76(1), 3–23. https://doi.org/10.1002/net.21932
- Street, A., Valladão, D., Lawson, A., & Velloso, A. (2020). Assessing the cost of the Hazard-Decision simplification in multistage stochastic hydrothermal scheduling. Applied Energy, 280, 115939. https://doi.org/10.1016/j.apenergy.2020.115939
-
$\begingroup$ First of all, thanks for the answer Penjhui!. In this regard, will all auxiliary variables become part of state for the decision hazard stage? $\endgroup$ Commented Jan 8, 2023 at 19:40
-
$\begingroup$ Yes, @Engr.MoizAhmad. The auxiliary variables are all state variables $aux_{t-1}$. What you want to optimize originally should be equal to these stage variables, i.e., $x_t = aux_{t-1}$. $\endgroup$ Commented Jan 8, 2023 at 19:49
-
$\begingroup$ So, @Penghui, according to your experience with stochastic dual dynamic programming (SDDP), is it a scalable way to handle hazard uncertainty when it comes to SDDP? $\endgroup$ Commented Jan 8, 2023 at 19:59
-
$\begingroup$ I already have 400 decision variables (all hazard decisions) and about 100 state variables in my practical sized supply chain problem. $\endgroup$ Commented Jan 8, 2023 at 20:00
-
$\begingroup$ @Engr.MoizAhmad I am also a beginner of SDDP, and do not have much computational experience. But it seems that SDDP can handle your problem with hundreds of variables efficiently, since the sub problems are Linear Programming. $\endgroup$ Commented Jan 8, 2023 at 20:54