An Approximation Scheme for Stochastic Integer Programs Arising in Capacity Expansion
- 1 June 2003
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 51 (3), 461-471
- https://doi.org/10.1287/opre.51.3.461.14960
Abstract
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.Keywords
This publication has 33 references indexed in Scilit:
- A scenario-based stochastic programming approach for technology and capacity planningComputers & Operations Research, 2002
- Analytical investigations of the process planning problemComputers & Chemical Engineering, 2000
- Capacity Optimization Planning System (CAPS)Informs Journal on Applied Analytics, 1999
- Robust Process Planning under UncertaintyIndustrial & Engineering Chemistry Research, 1998
- Lower Bounding Procedures for Multiperiod Telecommunications Network Expansion ProblemsOperations Research, 1995
- A stochastic optimization model for planning capacity expansion in a service industry under uncertain demandNaval Research Logistics (NRL), 1994
- The capacity expansion problem in the service industryComputers & Operations Research, 1994
- Telecommunications network topological design and capacity expansion: Formulations and algorithmsTelecommunication Systems, 1993
- Capacity Expansion Under Stochastic DemandsOperations Research, 1992
- Decomposition and Partitioning Methods for Multistage Stochastic Linear ProgramsOperations Research, 1985