| 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. |
