Optimization Online


A Multi-stage Stochastic Integer Programming Approach for Capacity Expansion under Uncertainty

Shabbir Ahmed (sahmed***at***isye.gatech.edu)
Alan J. King (kingaj***at***us.ibm.com)
Gyana Parija (parija***at***us.ibm.com)

Abstract: This paper addresses a multi-period investment model for capacity expansion in an uncertain environment. Using a scenario tree approach to model the evolution of uncertain demand and cost parameters, and fixed-charge cost functions to model the economies of scale in expansion costs, we develop a multi-stage stochastic integer programming formulation for the problem. A reformulation of the problem is proposed using variable disaggregation to exploit the lot-sizing substructure of the problem. The reformulation significantly reduces the LP relaxation gap of this large scale integer program. A heuristic scheme is presented to perturb the LP relaxation solutions to produce good quality integer solutions. Finally, we outline a branch and bound algorithm that makes use of the reformulation strategy as a lower bounding scheme, and the heuristic as an upper bounding scheme, to solve the problem to global optimality. Our preliminary computational results indicate that the proposed strategy has significant advantages over straightforward use of commercial solvers.

Keywords: capacity expansion, stochastic integer programming, reformulation, heuristic, branch and bound

Category 1: Stochastic Programming

Category 2: Integer Programming

Category 3: Applications -- OR and Management Sciences (Production and Logistics )

Citation: Journal of Global Optimization, vol. 26, pp.3-24, 2003.


Entry Submitted: 02/02/2001
Entry Accepted: 02/05/2001
Entry Last Modified: 06/09/2003

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society