Title:   Multi -stage Stochastic Programming for Network Capacity Expansion: Models and Algorithms

In networks, there are often more than one resource of capacity. The capacities can be permanently or temporarily owned by the decision maker. Depending on the nature of sources, we identify the permanent capacity, spot market capacity and contract capacity. We use a scenario tree to model the uncertainty, and build a multi-stage stochastic integer program that can incorporate multiple sources and multiple types of capacities in a general network. We study both the non-budget case and the budget case of the problem. To solve the non-budget case, we design an asymptotically convergent approximation algorithm. To solve the budget case, we design a Lagrangian Relaxation algorithm. The numerical experiments show superb performance of the proposed algorithms compared with commercial software.