Groupe d’études et de recherche en analyse des décisions


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


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