Back

G-2008-09

A Two-Level Interior-Point Decomposition Algorithm for Multi-Stage Stochastic Capacity Planning and Technology Acquisition

and

BibTeX reference

This paper describes a class of large-scale capacity planning problems under uncertainty. The uncertainty can arise in different dimensions of a production planning problem, and this paper is concerned with stochastic demand. Hence, we formulate a multi-stage stochastic program (MSP) to capture this uncertainty over time. Moreover, we implement a two-level, interior-point decomposition algorithm based on the analytic center cutting plane method (ACCPM) to solve the model. This decomposition is done on the dual of the problem to take advantage of the special structure of the MSP. The central prices obtained by the ACCPM provides a fast convergence and promising computational results in terms of the number of iterations. Finally, the resulting algorithm is compared against the two-level, classical Dantzig-Wolfe reformulation with a dynamic column generation.

, 18 pages

Research Axis

Research application

Publication

A two-level interior-point decomposition algorithm for multi-stage stochastic capacity planning and technology acquisition
and
International Journal of Mathematics in Operational Research, 3(3), 280–294, 2011 BibTeX reference