IRUS Total

Robust dual dynamic programming

File Description SizeFormat 
5752.pdfAccepted version2.6 MBAdobe PDFView/Open
Title: Robust dual dynamic programming
Authors: Georghiou, A
Tsoukalas, A
Wiesemann, W
Item Type: Journal Article
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 suboptimal 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 righthand 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 deterministic upper and lower bounds throughout the execution of the algorithm. We demonstrate the promising performance of our algorithm in a stylized inventory management problem.
Issue Date: 1-May-2019
Date of Acceptance: 29-Oct-2018
URI: http://hdl.handle.net/10044/1/65855
DOI: https://doi.org/10.1287/opre.2018.1835
ISSN: 0030-364X
Publisher: INFORMS (Institute for Operations Research and Management Sciences)
Start Page: 813
End Page: 830
Journal / Book Title: Operations Research
Volume: 67
Issue: 3
Copyright Statement: © 2019, INFORMS.
Sponsor/Funder: Engineering & Physical Science Research Council (E
Engineering & Physical Science Research Council (EPSRC)
Funder's Grant Number: EP/M028240/1
Keywords: Social Sciences
Science & Technology
Operations Research & Management Science
Business & Economics
robust optimization
multistage problems
dual dynamic programming
error bounds
0102 Applied Mathematics
0802 Computation Theory and Mathematics
1503 Business and Management
Operations Research
Publication Status: Published
Online Publication Date: 2019-04-03
Appears in Collections:Imperial College Business School