To main content

Progressive hedging for stochastic programs with cross-scenario inequality constraints

Progressive hedging for stochastic programs with cross-scenario inequality constraints

Category
Academic article
Abstract
In this paper, we show how progressive hedging may be used to solve stochastic programming problems that involve cross-scenario inequality constraints. In contrast, standard stochastic programs involve cross-scenario equality constraints that describe the non-anticipative nature of the optimal solution. The standard progressive hedging algorithm (PHA) iteratively manipulates the objective function coefficients of the scenario subproblems to reflect the costs of non-anticipativity and penalize deviations from a non-anticipative, aggregated solution. Our proposed algorithm follows the same principle, but works with cross-scenario inequality constraints. Specifically, we focus on the problem of determining optimal bids for hydropower producers that participate in wholesale electricity auctions. The cross-scenario inequality constraints arise from the fact that bids are required to be non-decreasing. We show that PHA for inequality constraints have the same convergence properties as standard PHA, and illustrate our algorithm with results for an instance of the hydropower bidding problem.
Client
  • Research Council of Norway (RCN) / 255100
  • Research Council of Norway (RCN) / 243964
Language
English
Affiliation
  • Norwegian University of Science and Technology
  • SINTEF Energy Research / Energisystemer
Year
2019
Published in
Computational Management Science
ISSN
1619-697X
Publisher
Springer
Volume
17
Issue
1
Page(s)
141 - 160