This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Ahmed, S. Articles by Sahinidis, N. V. Search for Related Content

An Approximation Scheme for Stochastic Integer Programs Arising in Capacity Expansion

School of Industrial and Systems Engineering, Georgia Institute of Technology, 765 Ferst Drive, Atlanta, Georgia 30332
Department of Chemical and Biomolecular Engineering, University of Illinois, 600 South Mathews Avenue, Urbana, Illinois 61801
sahmed{at}isye.gatech.edu
nikos{at}uiuc.edu

Planning for capacity expansion forms a crucial part of the strategic-level decision making in many applications. Consequently, quantitative models for economic capacity expansion planning have been the subject of intense research. However, much of the work in this area has been restricted to linear cost models and/or limited degree of uncertainty to make the problems analytically tractable. This paper addresses a stochastic capacity expansion problem where the economies-of-scale in expansion costs are handled via fixed-charge cost functions, and forecast uncertainties in the problem parameters are explicitly considered by specifying a set of scenarios. The resulting formulation is a multistage stochastic integer program. We develop a fast, linear-programming-based, approximation scheme that exploits the decomposable structure and is guaranteed to produce feasible solutions for this problem. Through a probabilistic analysis, we prove that the optimality gap of the heuristic solution almost surely vanishes asymptotically as the problem size increases.

Subject classifications: Analysis of algorithms: asymptotically optimal heuristics; Facilities/equipment planning: capacity expansion; Programming: stochastic, integer.