Optimization Online


Robust Dual Dynamic Programming

Angelos Georghiou (angelos.georghiou***at***mcgill.ca)
Angelos Tsoukalas (angelos.tsoukalas***at***aub.edu.lb)
Wolfram Wiesemann (ww***at***imperial.ac.uk)

Abstract: Multi-stage robust optimization problems, where the decision maker can dynamically react to consecutively observed realizations of the uncertain problem parameters, pose formidable theoretical and computational challenges. As a result, the existing solution approaches for this problem class typically determine subopti- mal solutions under restrictive assumptions. In this paper, we propose a robust dual dynamic programming (RDDP) scheme for multi-stage robust optimization problems. The RDDP scheme takes advantage of the decomposable nature of these problems by bounding the costs arising in the future stages through lower and upper cost to-go functions. For problems with uncertain technology matrices and/or constraint right- hand sides, our RDDP scheme determines an optimal solution in finite time. If also the objective function and/or the recourse matrices are uncertain, our method converges asymptotically (but deterministically) to an optimal solution. Our RDDP scheme does not require a relatively complete recourse, and it offers deter- ministic upper and lower bounds throughout the execution of the algorithm. We demonstrate the promising performance of our algorithm in stylized instances of inventory management and energy planning problems.

Keywords: robust optimization, multi-stage problems, dual dynamic programming, error bounds

Category 1: Robust Optimization


Download: [PDF]

Entry Submitted: 12/01/2016
Entry Accepted: 12/01/2016
Entry Last Modified: 11/03/2017

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