Stochastic Integer Programming: Decomposition Methods and Industrial Applications

Many practical problems from industry that contain uncertain demands, costs and other quantities are challenging to solve. Stochastic Mixed Integer Programs (SMIPs) have become an emerging tool to incorporate uncertainty in optimization problems. The stochastic and mixed integer nature of SMIPs makes them very challenging to solve. Decomposition methods have been developed to solve various practical problems modeled as large-scale SMIPs. In the thesis, we propose a scenario-wise decomposition method, the Dynamic Dual Decomposition method ($D^3$ method), to decompose large-scale SMIPs in order to solve practical facility location problems more efficiently. The Lagrangian bounds are dynamically determined. We also consider alternative ways to represent non-anticipativity conditions to improve computational performance. The $D^3$ method efficiently solved moderate and large sized instances whose deterministic equivalent problem could not be solved or solved much slower by a state-of-the-art commercial solver. Three-stage models are also studied and solved by the $D^3$ method, which is found to be effective as well. We combine the $D^3$ method and Column Generation approach to solve a stochastic version of the set packing problem. The proposed method is quite effective in numerical experiments and outperforms the commercial solver dramatically in most cases. We study the sensitivity of different density of patterns and find our proposed method is more robust than solving the whole problem by the commercial solver or by implementing the conventional column generation method directly.We use the $D^3$ method as a framework and combine it with Benders Decomposition Method (BDM) to solve the Stochastic Multi-plant Facility Location Problem. The mathematical formulation of the model is a two-stage SMIP problem with integer first stage variables and mixed integer second stage variables. The integer variables in both stages cause the large-scale SMIP model to be intractable. Some strategies for accelerating BDM have been developed in solving scenario subproblems which are decomposed by $D^3$ method. We develop the aggregation method to aggregate scenarios in solving decomposed Benders Dual subproblems and approximate the solution of the original problems. Our computational experiments on benchmark data and randomly generated data shows that the proposed method can solve large-sized problems more efficiently than conventional Benders Decomposition or a commercial solver. The computational comparisons also show that the aggregation method can reduce the number of scenarios in large problems and obtain approximately optimal solutions in much shorter computational time.Ph.D