An Approximation Scheme for Stochastic Integer Programs Arising in Capacity Expansion

Shabbir Ahmed () and Nikolaos V. Sahinidis ()
Additional contact information
Shabbir Ahmed: School of Industrial and Systems Engineering, Georgia Institute of Technology, 765 Ferst Drive, Atlanta, Georgia 30332
Nikolaos V. Sahinidis: Department of Chemical and Biomolecular Engineering, University of Illinois, 600 South Mathews Avenue, Urbana, Illinois 61801

Operations Research, 2003, vol. 51, issue 3, 461-471

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: Analysis of algorithms: asymptotically optimal heuristics; Facilities/equipment planning: capacity expansion; Programming: stochastic; integer (search for similar items in EconPapers)
Date: 2003
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (25)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.51.3.461.14960 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:51:y:2003:i:3:p:461-471

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().