An approximation scheme for stochastic integer programs arising in capacity expansion

作     者：Ahmed, S Sahinidis, NV 

作者机构：Georgia Inst Technol Sch Ind & Syst Engn Atlanta GA 30332 USA Univ Illinois Dept Chem & Biomol Engn Urbana IL 61801 USA 

出 版 物：《OPERATIONS RESEARCH》 (运筹学)

年 卷 期：2003年第51卷第3期

页      面：461-471页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主　　题：Analysis of algorithms: asymptotically optimal heuristics Facilities/equipment planning: capacity expansion Programming: stochastic integer 

摘      要：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.