Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


Chennan_Zhou_Dissertation.pdf (2.58 MB)

ETD Abstract Container

Abstract Header

Effective Scenarios in Distributionally Robust Optimization: Properties and Acceleration of Decomposition Algorithms

Zhou, Chennan
http://rave.ohiolink.edu/etdc/view?acc_num=osu1713506263747318

Abstract Details

2024, Doctor of Philosophy, Ohio State University, Industrial and Systems Engineering.
Decision-making problems in real life often involve uncertainties. One way to address such problems is to use stochastic optimization, where quantifying a probability distribution to represent the underlying uncertainty is critical. However, most often, only partial information about the uncertainty is available through a series of historical data and expert knowledge. This limitation becomes particularly significant if the decision maker is risk averse and needs to consider rare but high-impact events, for which the probability distribution cannot be accurately determined even with the available historical data. Distributionally Robust Stochastic Optimization (DRO) is an alternative approach that assumes that the underlying distribution is unknown but instead lies in an ambiguity set of distributions that is consistent with the available data. DRO then tries to optimize the worst-case expectation among all distributions in the ambiguity set. This dissertation focuses on effective scenarios in DROs defined using a finite number of realizations (also called scenarios) of the uncertain parameters. Effective scenarios are the critical scenarios in DRO in the sense that their removal alters the optimal objective function value. Ineffective scenarios, on the other hand, can be removed safely without changing the optimal value. In this dissertation, we investigate both the theoretical and computational aspects of effective scenarios. The first contribution of this dissertation links the effectiveness of a scenario to its worst-case distribution being always positive or uniquely zero under a general ambiguity set with finite support. We then narrow down our focus to DROs with ambiguity sets formed via the Cressie-Read power divergence family (DRO-CR) and the Wasserstein distance (DRO-W). This class of problems constitutes some of the most widely used DROs in the literature. We provide easy-to-check sufficient conditions to identify the effectiveness of scenarios for this class of problems. We illustrate our theoretical findings through numerical results conducted on test problems from the literature. Particularly, we (i) examine the performance of the easy-to-check conditions, (ii) study how the effectiveness of scenarios relates to their cost at the optimal solution, and (iii) compare the characteristics of various DRO-CRs with each other and with DRO-W. For DRO-CR, we propose a bisection algorithm to solve the worst-case expected problem that significantly outperforms existing methods. Lastly, for DRO-W, we investigate how the problem characteristics may impact the effectiveness of scenarios. The final contribution of this dissertation proposes a novel approach to accelerate Benders' decomposition algorithm using effective scenarios. During each Benders' iteration, we estimate the set of effective scenarios and focus the algorithm's effort on such scenarios. Our method combines the ideas of scenario reduction and controlling Benders cuts, and to the best of our knowledge is the first one that uses scenario reduction strategies to solve fewer second-stage problems. Numerical results on several problems from the literature show that the accelerated algorithm runs up to 50 times faster on large-scale problems, obtaining high-quality solutions.
Guzin Bayraksan (Advisor)
Sam Davanloo (Committee Member)
Cathy Xia (Committee Member)
Industrial Engineering; Operations Research
Distributionally robust stochastic optimization, Effective scenario, Optimization under uncertainty

Recommended Citations

Citations

  • Zhou, C. (2024). Effective Scenarios in Distributionally Robust Optimization: Properties and Acceleration of Decomposition Algorithms [Doctoral dissertation, Ohio State University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=osu1713506263747318

    APA Style (7th edition)

  • Zhou, Chennan. Effective Scenarios in Distributionally Robust Optimization: Properties and Acceleration of Decomposition Algorithms. 2024. Ohio State University, Doctoral dissertation. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=osu1713506263747318.

    MLA Style (8th edition)

  • Zhou, Chennan. "Effective Scenarios in Distributionally Robust Optimization: Properties and Acceleration of Decomposition Algorithms." Doctoral dissertation, Ohio State University, 2024. http://rave.ohiolink.edu/etdc/view?acc_num=osu1713506263747318

    Chicago Manual of Style (17th edition)

osu1713506263747318
85
© 2024, all rights reserved.
This open access ETD is published by The Ohio State University and OhioLINK.