We propose a nested decomposition scheme for infinite-horizon stochastic linear programs. Our approach can be seen as a provably convergent extension of stochastic dual dynamic programming to the infinite-horizon setting: we explore a sequence of finite-horizon problems of increasing length until we can guarantee convergence with a given confidence level. The methodology alternates between a forward pass to explore sample paths and determine trial solutions, and a backward pass to generate a polyhedral approximation of the optimal value function by computing subgradients from the dual of the scenario subproblems. A computational study on a large set of randomly generated instances for two classes of problems shows that the proposed algorithm is able to effectively solve instances of moderate size to high precision, provided that the instance structure allows the construction of what we call constant-statepolicies with satisfactory objective function value.

A Benders squared (B2) framework for infinite-horizon stochastic linear programs

Roberto Wolfler Calvo
2021-01-01

Abstract

We propose a nested decomposition scheme for infinite-horizon stochastic linear programs. Our approach can be seen as a provably convergent extension of stochastic dual dynamic programming to the infinite-horizon setting: we explore a sequence of finite-horizon problems of increasing length until we can guarantee convergence with a given confidence level. The methodology alternates between a forward pass to explore sample paths and determine trial solutions, and a backward pass to generate a polyhedral approximation of the optimal value function by computing subgradients from the dual of the scenario subproblems. A computational study on a large set of randomly generated instances for two classes of problems shows that the proposed algorithm is able to effectively solve instances of moderate size to high precision, provided that the instance structure allows the construction of what we call constant-statepolicies with satisfactory objective function value.
2021
Benders decomposition
Cutting planes
Stochastic programming
File in questo prodotto:
File Dimensione Formato  
MathProgrammingComp2021.pdf

Solo gestori archivio

Descrizione: VoR
Tipologia: versione editoriale (VoR)
Dimensione 478.21 kB
Formato Adobe PDF
478.21 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11584/434026
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact