| Multi-stage robust optimization and stochastic programming are two approaches for multi-stage decision making under data uncertainty. In this dissertation, three problems on multi-stage robust optimization and stochastic programming are discussed.;First, we consider a robust lot-sizing problem as an example to analyze multi-stage robust integer programming problems. In the robust lot-sizing problem setting, we consider the cases in which severe events may happen such that the normal process will be disrupted. Our objective is to provide a robust schedule such that the total cost is minimized under the worst case scenario. This problem can be formulated as a multi-stage robust integer programming problem. Several cases are studied and corresponding algorithms are developed. Our preliminary study verifies the effectiveness of our approaches.;Second, we consider two-stage stochastic uncapacitated lot-sizing problems with deterministic demands and Wagner-Whitin costs. We develop extended formulations in the higher dimensional space that can provide integral solutions by showing that their constraint matrices are totally unimodular. For the case without backlogging, we provide the convex hull description of the problem in the original space by projecting the extended formulation to the original space. For the case with backlogging, we provide a tighter extended formulation by projecting the extended formulation to a lower dimensional space.;Third, we study a general stochastic dynamic knapsack polytope. We apply the pairing, mixing, and lifting schemes to the stochastic dynamic knapsack set and obtain strong valid inequalities. We investigate the algorithmic and implementation issues for the effective and efficient generation of lifted valid inequalities of the stochastic dynamic knapsack polytope in a parallel computing environment. The speedup, communication overhead, load balance, and effectiveness in closing the integrality gap for stochastic dynamic knapsack polytope are studied. Computational experiments show the effectiveness of our proposed approaches. |
