Saleck Pay, Babak.
Decomposition Algorithms in Stochastic Integer Programming: Applications and Computations.
Degree: PhD, Mathematical Sciences, 2017, Virginia Commonwealth University
In this dissertation we focus on two main topics. Under the first topic, we develop a new framework for stochastic network interdiction problem to address ambiguity in the defender risk preferences. The second topic is dedicated to computational studies of two-stage stochastic integer programs. More specifically, we consider two cases. First, we develop some solution methods for two-stage stochastic integer programs with continuous recourse; second, we study some computational strategies for two-stage stochastic integer programs with integer recourse.
We study a class of stochastic network interdiction problems where the defender has incomplete (ambiguous) preferences. Specifically, we focus on the shortest path network interdiction modeled as a Stackelberg game, where the defender (leader) makes an interdiction decision first, then the attacker (follower) selects a shortest path after the observation of random arc costs and interdiction effects in the network. We take a decision-analytic perspective in addressing probabilistic risk over network parameters, assuming that the defender's risk preferences over exogenously given probabilities can be summarized by the expected utility theory. Although the exact form of the utility function is ambiguous to the defender, we assume that a set of historical data on some pairwise comparisons made by the defender is available, which can be used to restrict the shape of the utility function. We use two different approaches to tackle this problem. The first approach conducts utility estimation and optimization separately, by first finding the best fit for a piecewise linear concave utility function according to the available data, and then optimizing the expected utility. The second approach integrates utility estimation and optimization, by modeling the utility ambiguity under a robust optimization framework following and . We conduct extensive computational experiments to evaluate the performances of these approaches on the stochastic shortest path network interdiction problem.
In third chapter, we propose partition-based decomposition algorithms for solving two-stage stochastic integer program with continuous recourse. The partition-based decomposition method enhance the classical decomposition methods (such as Benders decomposition) by utilizing the inexact cuts (coarse cuts) induced by a scenario partition. Coarse cut generation can be much less expensive than the standard Benders cuts, when the partition size is relatively small compared to the total number of scenarios. We conduct an extensive computational study to illustrate the advantage of the proposed partition-based decomposition algorithms compared with the state-of-the-art approaches.
In chapter four, we concentrate on computational methods for two-stage stochastic integer program with integer recourse. We consider the partition-based relaxation framework integrated with a scenario decomposition algorithm in order to develop strategies which provide a better lower…
Advisors/Committee Members: Dr. Yongjia Song.
Subjects/Keywords: Stochastic Network Interdiction; Incomplete Preferences Information; Two-stage Stochastic Integer Programming; Industrial Engineering; Operational Research; Other Operations Research, Systems Engineering and Industrial Engineering; Systems Engineering
…Commonwealth University, 2017.
Director: Dr. Yongjia Song, Assistant Professor
Department of… …requirements for the degree of
Doctor of Philosophy at Virginia Commonwealth University.
to Zotero / EndNote / Reference
APA (6th Edition):
Saleck Pay, B. (2017). Decomposition Algorithms in Stochastic Integer Programming: Applications and Computations. (Doctoral Dissertation). Virginia Commonwealth University. Retrieved from https://scholarscompass.vcu.edu/etd/5027
Chicago Manual of Style (16th Edition):
Saleck Pay, Babak. “Decomposition Algorithms in Stochastic Integer Programming: Applications and Computations.” 2017. Doctoral Dissertation, Virginia Commonwealth University. Accessed October 15, 2019.
MLA Handbook (7th Edition):
Saleck Pay, Babak. “Decomposition Algorithms in Stochastic Integer Programming: Applications and Computations.” 2017. Web. 15 Oct 2019.
Saleck Pay B. Decomposition Algorithms in Stochastic Integer Programming: Applications and Computations. [Internet] [Doctoral dissertation]. Virginia Commonwealth University; 2017. [cited 2019 Oct 15].
Available from: https://scholarscompass.vcu.edu/etd/5027.
Council of Science Editors:
Saleck Pay B. Decomposition Algorithms in Stochastic Integer Programming: Applications and Computations. [Doctoral Dissertation]. Virginia Commonwealth University; 2017. Available from: https://scholarscompass.vcu.edu/etd/5027