Optimization Online


Optimal scenario set partitioning for multistage stochastic programming with the progressive hedging algorithm

Pierre-Luc Carpentier(plcarpentier***at***gmail.com)
Michel Gendreau(michel.gendreau***at***cirrelt.ca)
Fabian Bastin(bastin***at***iro.umontreal.ca)

Abstract: In this paper, we propose a new approach to reduce the total running time (RT) of the progressive hedging algorithm (PHA) for solving multistage stochastic programs (MSPs) defined on a scenario tree. Instead of using the conventional scenario decomposition scheme, we apply a multi-scenario decomposition scheme and partition the scenario set in order to minimize the number of non-anticipativity constraints (NACs) on which an augmented Lagrangian relaxation (ALR) must be applied. Our partitioning method is a heuristic algorithm that takes into account the complex branching structure of general multistage scenario trees. Minimizing the number of relaxed NACs (RNACs) enhances the PHA's convergence rate by decreasing the variability of subproblems solutions at duplicated tree nodes. This is due to the fact that minimizing the RNACs reduces the anticipativity level of subproblems by increasing the branching level of subtrees. This makes RNACs easier to satisfy. Our partitioning method also reduces the total RT per iteration in two different ways. Firstly, it decreases the number of linear and quadratic penalty terms that need to be included in subproblems objective function. Secondly, it reduces the total number of duplicated decision variables and constraints at tree nodes that are associated with RNACs. The proposed method is tested on an hydroelectricity generation scheduling problem covering a 52 weeks planning horizon.

Keywords: Stochastic programming, Augmented Lagrangian, Scenario tree, Progressive hedging

Category 1: Stochastic Programming


Download: [PDF]

Entry Submitted: 10/03/2013
Entry Accepted: 10/03/2013
Entry Last Modified: 10/03/2013

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 Optimization Society