Efficient solution procedures for multistage stochastic formulations of two problem classes

Most real world optimization problems include uncertainty in the problem parameters, which are usually defined by probability distributions. Stochastic programming is used to model such problems, where the goal is to determine a policy that minimizes or maximizes the expectation of a function of the problem parameters and decision variables. However, a major drawback of stochastic programming models is that their size and complexity grow exponentially with the number of input parameters. Therefore, realistic instances of stochastic programs are large scale optimization models, for which efficient solution procedures need to be developed. We consider two classes of stochastic programming models which are motivated by two applications related to the field of aviation. These applications are used to develop models and solution procedures for two general problem classes, namely the stochastic network capacity planning problem and the project portfolio optimization problem.; The first stochastic programming problem we consider is the network capacity planning problem, which arises in capacity planning of systems with network structures, such as transportation terminals, roadways and telecommunication networks. We study this problem in the context of airport terminal capacity planning, and infer results for the general class of such problems. In the airport terminal capacity planning problem, the objective is to determine the optimal design and expansion capacities for different areas of the terminal in the presence of uncertainty in future demand levels and expansion costs, such that overall passenger delay is minimized. We model this problem as a nonlinear multistage stochastic integer program, which contains a multicommodity network flow structure representing the flow of passengers in the terminal. The formulation requires the use of time functions for maximum delays in passageways and processing stations, for which we derive approximations that account for the transient behavior of passenger flow. The deterministic equivalent of the developed stochastic programming model is solved via a branch and bound procedure, in which a bounding heuristic is used at the nodes of the branch and bound tree to obtain integer solutions. This improved approach is shown to be significantly effective in reducing the solution time of the problem over standard approaches.; In the second study, we consider the project portfolio optimization problem. This problem falls in the class of stochastic programs in which times of uncertainty realizations are dependent on the decisions made. We study this problem within the context of optimizing aviation technology development portfolios. In this problem, the amount of investment in a given technology project determines when the uncertainty in the performance of the technology is revealed. In general, the project portfolio management problem deals with the selection of research and development (R&D) projects and determination of optimal resource allocations for the current planning period such that the expected total discounted return or a function of this expectation for all projects over an infinite time horizon is maximized, given the uncertainties and resource limitations over a planning horizon. The problem contains endogenous stochastic parameters, i.e. some parameters such as the returns are known only after making an investment. Accounting for this endogeneity, we propose efficient modeling and solution approaches for the resulting multistage stochastic integer programming model. We first develop a formulation that is amenable to scenario decomposition, and is applicable to the general class of stochastic problems with endogenous uncertainty. We then demonstrate the use of the sample average approximation method in solving large scale problems of this class, where the sample problems are solved through Lagrangian relaxation and lower bounding heuristics.; Practical and theoretical contributions of the...