Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


osu1275433024.pdf (1.32 MB)

ETD Abstract Container

Abstract Header

Algorithmic Advances in Stochastic Combinatorial Optimization and Applications

Yuan, Yang
http://rave.ohiolink.edu/etdc/view?acc_num=osu1275433024

Abstract Details

2010, Doctor of Philosophy, Ohio State University, Industrial and Systems Engineering.
In this dissertation, we study two-stage stochastic combinatorial optimization (SCO) problems in which both first and second stage decisions include some binary variables. The common theme is the use of decomposition techniques together with valid inequalities to solve these problems. Potential computational speed-ups are first explored in solving SCOs with pure binary first-stage variables and mixed-binary second-stage variables. We propose new cuts of value function convexification, and a decomposition procedure for cut generation for the second-stage mixed-integer programming problem. These enhancements result in approximately 50% reduction in CPU time, compared to the best performance reported in the literature. Next, we develop a coupled branch-and-bound algorithm for a broader class of stochastic mixed-integer programming problems allowing continuous as well as integer variables in both stages. We present the finite convergence property of this algorithm, and illustrate the method via a numerical instance. We next allow the random variables in the model to have infinitely many outcomes, and propose the first decomposition-based sequential sampling algorithm for two-stage SCOs. Asymptotic convergence properties of this algorithm are presented and preliminary computational results are also reported. Finally, we develop a stochastic mixed-integer programming model to design the next-generation IP-over-optical network. Such network must ensure the feasibility of the state-of-the-art network restoration under any potential network failure. We propose customized decomposition methods and corresponding valid inequalities to solve large-scale practical instances.
Suvrajeet Sen, PhD (Committee Chair)
Julia Higle, PhD (Committee Member)
Simge Kucukyavuz, PhD (Committee Member)
Operations Research

Recommended Citations

Citations

  • Yuan, Y. (2010). Algorithmic Advances in Stochastic Combinatorial Optimization and Applications [Doctoral dissertation, Ohio State University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=osu1275433024

    APA Style (7th edition)

  • Yuan, Yang. Algorithmic Advances in Stochastic Combinatorial Optimization and Applications. 2010. Ohio State University, Doctoral dissertation. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=osu1275433024.

    MLA Style (8th edition)

  • Yuan, Yang. "Algorithmic Advances in Stochastic Combinatorial Optimization and Applications." Doctoral dissertation, Ohio State University, 2010. http://rave.ohiolink.edu/etdc/view?acc_num=osu1275433024

    Chicago Manual of Style (17th edition)

osu1275433024
869
© 2010, all rights reserved.
This open access ETD is published by The Ohio State University and OhioLINK.