Article ID: | iaor20108089 |
Volume: | 22 |
Issue: | 4 |
Start Page Number: | 543 |
End Page Number: | 554 |
Publication Date: | Sep 2010 |
Journal: | INFORMS Journal on Computing |
Authors: | Watson Jean-Paul, Woodruff David L, Wets Roger J-B |
Keywords: | chance-constrained optimisation, Lagrangian relaxation |
We describe computational procedures for solving a wide-ranging class of stochastic programs with chance constraints where the random components of the problem are discretely distributed. Our procedures are based on a combination of Lagrangian relaxation and scenario decomposition, which we solve using a novel variant of Rockafellar and Wets' progressive hedging algorithm (1991). Experiments demonstrate the ability of the proposed algorithm to quickly find near-optimal solutions–where verifiable–to both difficult and very large chance-constrained stochastic programs, both with and without integer decision variables. The algorithm exhibits strong scalability in terms of both run time required and final solution quality on large-scale instances.