東華大學圖書館 |

Multistage Stochastic Programming: Algorithms, Modelling and Applications.

紀錄類型:	書目-電子資源 : Monograph/item
正題名/作者:	Multistage Stochastic Programming: Algorithms, Modelling and Applications./
作者:	Siddig, Murwan.
出版者:	Ann Arbor : ProQuest Dissertations & Theses, : 2021,
面頁冊數:	165 p.
附註:	Source: Dissertations Abstracts International, Volume: 83-03, Section: B.
Contained By:	Dissertations Abstracts International83-03B.
標題:	Industrial engineering. -
電子資源:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=28645082
ISBN:	9798544278900

Multistage Stochastic Programming: Algorithms, Modelling and Applications.
Siddig, Murwan.

Multistage Stochastic Programming: Algorithms, Modelling and Applications. - Ann Arbor : ProQuest Dissertations & Theses, 2021 - 165 p.

Source: Dissertations Abstracts International, Volume: 83-03, Section: B.

Thesis (Ph.D.)--Clemson University, 2021.

This item must not be sold to any third party vendors.

This dissertation comprises four different topics related to multistage stochastic programming (MSP) algorithms, modeling, and applications.First, we extend the adaptive partition-based approach for solving two-stage stochastic programs with a fixed recourse matrix and a fixed cost vector to the MSP setting, where the stochastic process is assumed to be stage-wise independent. The proposed algorithms integrate the adaptive partition-based strategy with a popular approach for solving multistage stochastic programs, the stochastic dual dynamic programming (SDDP) algorithm, according to two main strategies. These two strategies are distinct from each other in the manner by which they refine the partitions during the solution process. In particular, we propose a refinement outside SDDP strategy whereby we iteratively solve a coarse scenario tree induced by the partitions and refine the partitions in a separate step outside of SDDP, only when necessary. We also propose a refinement within SDDP strategy where the partitions are refined in conjunction with the machinery of the SDDP algorithm. We then use, within the two different refinement schemes, different tree-traversal strategies, which allow us to have some control over the size of the partitions. Our numerical experiments on a hydro-thermal power generation planning problem show the effectiveness of the proposed algorithms in comparison to the standard SDDP algorithm. Moreover, the results show that the algorithms with the refinement outside SDDP strategy outperform the ones with the refinement within SDDP strategy.Second, we study an important question related to solving MSP problems with a large number of stages. A common approach to tackle MSP problems with a large number of stages is a rolling-horizon (RH) procedure, where one solves a sequence of MSP problems with a smaller number of stages. This leads to a delicate issue of how many stages to include in the smaller problems used in the RH procedure. We study this question for both finite and infinite horizon MSP problems where the stochastic process is assumed to be stationary. For the infinite horizon case with discounted costs, we derive a bound which can be used to prescribe an epsilon-sufficient number of stages. For the finite horizon case, we propose a heuristic approach from the perspective of approximate dynamic programming to provide a sufficient number of stages for each roll in the RH procedure. Our numerical experiments on a hydrothermal power generation planning problem show the effectiveness of the proposed approaches.Third, we introduce a computationally practical approach for solving a class of partially observable multistage stochastic programming problems. In this class of problems, the underlying stochastic process is assumed to follow a hidden Markov chain. Recent advances in the literature introduce a derivative of the SDDP method, known as the partially observable SDDP algorithm. This approach, however, introduces a belief-state vector to the stochastic programming formulation, which increases the computation significantly. Instead, we solve the problem assuming that this Markov chain is fully observable. However, when evaluating the resulting policy, we use a Bayesian update of the belief vector and use the state's decisions that have the highest posterior. Our numerical experiments on a hydrothermal planning problem show the practicality of this approach.Fourth, we consider a typical logistics planning problem for prepositioning relief items in preparation for an impending hurricane landfall. In this problem, the goal of the decision-maker is to improve the post-disaster relief effort by prepositioning relief items, over multiple periods, at different supply points while minimizing the total cost. The total cost consists of the logistics costs and a penalty for failing to satisfy the demand (if any shortage is present). We assume that the demand for relief items can be derived from two of the hurricane characteristics, namely, its intensity and landfall location. However, since these characteristics cannot be known in advance, we assume that they evolve and can be modeled as a Markov chain. We consider this problem in two different settings: first, we assume that the time of landfall is deterministic and known a priori, and second, we assume that it is random. To solve the resulting decision problem in each setting, we feed the Markov chain into a fully adaptive MSP model. This MSP model allows the decision-maker to adapt their operational logistics decisions sequentially, over multiple stages, as the hurricane's landfall characteristics become more and more clear. We test each MSP model in a case study and compare its performance to a clairvoyance solution and other alternative approximation policies. Our numerical results provide several insights into the value of using an MSP model the adaptive logistics planning for hurricane relief.

ISBN: 9798544278900Subjects--Topical Terms:

526216
Industrial engineering.
Subjects--Index Terms:

Multistage Stochastic Programming

Multistage Stochastic Programming: Algorithms, Modelling and Applications.
LDR:06213nmm a2200397 4500 001 2347927
005 20220829094953.5
008 241004s2021 ||||||||||||||||| ||eng d
020 $a 9798544278900
035 $a (MiAaPQ)AAI28645082
035 $a AAI28645082
040 $a MiAaPQ $c MiAaPQ
100 1 $a Siddig, Murwan. $3 3687237
245 1 0 $a Multistage Stochastic Programming: Algorithms, Modelling and Applications.
260 1 $a Ann Arbor : $b ProQuest Dissertations & Theses, $c 2021
300 $a 165 p.
500 $a Source: Dissertations Abstracts International, Volume: 83-03, Section: B.
500 $a Advisor: Song, Yongjia.
502 $a Thesis (Ph.D.)--Clemson University, 2021.
506 $a This item must not be sold to any third party vendors.
520 $a This dissertation comprises four different topics related to multistage stochastic programming (MSP) algorithms, modeling, and applications.First, we extend the adaptive partition-based approach for solving two-stage stochastic programs with a fixed recourse matrix and a fixed cost vector to the MSP setting, where the stochastic process is assumed to be stage-wise independent. The proposed algorithms integrate the adaptive partition-based strategy with a popular approach for solving multistage stochastic programs, the stochastic dual dynamic programming (SDDP) algorithm, according to two main strategies. These two strategies are distinct from each other in the manner by which they refine the partitions during the solution process. In particular, we propose a refinement outside SDDP strategy whereby we iteratively solve a coarse scenario tree induced by the partitions and refine the partitions in a separate step outside of SDDP, only when necessary. We also propose a refinement within SDDP strategy where the partitions are refined in conjunction with the machinery of the SDDP algorithm. We then use, within the two different refinement schemes, different tree-traversal strategies, which allow us to have some control over the size of the partitions. Our numerical experiments on a hydro-thermal power generation planning problem show the effectiveness of the proposed algorithms in comparison to the standard SDDP algorithm. Moreover, the results show that the algorithms with the refinement outside SDDP strategy outperform the ones with the refinement within SDDP strategy.Second, we study an important question related to solving MSP problems with a large number of stages. A common approach to tackle MSP problems with a large number of stages is a rolling-horizon (RH) procedure, where one solves a sequence of MSP problems with a smaller number of stages. This leads to a delicate issue of how many stages to include in the smaller problems used in the RH procedure. We study this question for both finite and infinite horizon MSP problems where the stochastic process is assumed to be stationary. For the infinite horizon case with discounted costs, we derive a bound which can be used to prescribe an epsilon-sufficient number of stages. For the finite horizon case, we propose a heuristic approach from the perspective of approximate dynamic programming to provide a sufficient number of stages for each roll in the RH procedure. Our numerical experiments on a hydrothermal power generation planning problem show the effectiveness of the proposed approaches.Third, we introduce a computationally practical approach for solving a class of partially observable multistage stochastic programming problems. In this class of problems, the underlying stochastic process is assumed to follow a hidden Markov chain. Recent advances in the literature introduce a derivative of the SDDP method, known as the partially observable SDDP algorithm. This approach, however, introduces a belief-state vector to the stochastic programming formulation, which increases the computation significantly. Instead, we solve the problem assuming that this Markov chain is fully observable. However, when evaluating the resulting policy, we use a Bayesian update of the belief vector and use the state's decisions that have the highest posterior. Our numerical experiments on a hydrothermal planning problem show the practicality of this approach.Fourth, we consider a typical logistics planning problem for prepositioning relief items in preparation for an impending hurricane landfall. In this problem, the goal of the decision-maker is to improve the post-disaster relief effort by prepositioning relief items, over multiple periods, at different supply points while minimizing the total cost. The total cost consists of the logistics costs and a penalty for failing to satisfy the demand (if any shortage is present). We assume that the demand for relief items can be derived from two of the hurricane characteristics, namely, its intensity and landfall location. However, since these characteristics cannot be known in advance, we assume that they evolve and can be modeled as a Markov chain. We consider this problem in two different settings: first, we assume that the time of landfall is deterministic and known a priori, and second, we assume that it is random. To solve the resulting decision problem in each setting, we feed the Markov chain into a fully adaptive MSP model. This MSP model allows the decision-maker to adapt their operational logistics decisions sequentially, over multiple stages, as the hurricane's landfall characteristics become more and more clear. We test each MSP model in a case study and compare its performance to a clairvoyance solution and other alternative approximation policies. Our numerical results provide several insights into the value of using an MSP model the adaptive logistics planning for hurricane relief.
590 $a School code: 0050.
650 4 $a Industrial engineering. $3 526216
650 4 $a Business administration. $3 3168311
650 4 $a Logic. $3 529544
653 $a Multistage Stochastic Programming
653 $a Stochastic Dual Dynamic Programming
653 $a Algorithms
653 $a Hydrothermal power generation
653 $a Logistics costs
653 $a Decision making
653 $a Planning
690 $a 0546
690 $a 0310
690 $a 0395
710 2 $a Clemson University. $b College of Engineering, Computing and Applied Sciences. $3 3545545
773 0 $t Dissertations Abstracts International $g 83-03B.
790 $a 0050
791 $a Ph.D.
792 $a 2021
793 $a English
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=28645082