Skip to main content

Information relaxations, duality, and convex stochastic dynamic programs

Publication ,  Journal Article
Brown, DB; Smith, JE
Published in: Operations Research
November 1, 2014

We consider the information relaxation approach for calculating performance bounds for stochastic dynamic programs (DPs). This approach generates performance bounds by solving problems with relaxed nonanticipativity constraints and a penalty that punishes violations of these nonanticipativity constraints. In this paper, we study DPs that have a convex structure and consider gradient penalties that are based on first-order linear approximations of approximate value functions. When used with perfect information relaxations, these penalties lead to subproblems that are deterministic convex optimization problems. We show that these gradient penalties can, in theory, provide tight bounds for convex DPs and can be used to improve on bounds provided by other relaxations, such as Lagrangian relaxation bounds. Finally, we apply these results in two example applications: first, a network revenue management problem that describes an airline trying to manage seat capacity on its flights; and second, an inventory management problem with lead times and lost sales. These are challenging problems of significant practical interest. In both examples, we compute performance bounds using information relaxations with gradient penalties and find that some relatively easy-to-compute heuristic policies are nearly optimal.

Duke Scholars

Published In

Operations Research

DOI

EISSN

1526-5463

ISSN

0030-364X

Publication Date

November 1, 2014

Volume

62

Issue

6

Start / End Page

1394 / 1415

Related Subject Headings

  • Operations Research
  • 3507 Strategy, management and organisational behaviour
  • 1503 Business and Management
  • 0802 Computation Theory and Mathematics
  • 0102 Applied Mathematics
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Brown, D. B., & Smith, J. E. (2014). Information relaxations, duality, and convex stochastic dynamic programs. Operations Research, 62(6), 1394–1415. https://doi.org/10.1287/opre.2014.1322
Brown, D. B., and J. E. Smith. “Information relaxations, duality, and convex stochastic dynamic programs.” Operations Research 62, no. 6 (November 1, 2014): 1394–1415. https://doi.org/10.1287/opre.2014.1322.
Brown DB, Smith JE. Information relaxations, duality, and convex stochastic dynamic programs. Operations Research. 2014 Nov 1;62(6):1394–415.
Brown, D. B., and J. E. Smith. “Information relaxations, duality, and convex stochastic dynamic programs.” Operations Research, vol. 62, no. 6, Nov. 2014, pp. 1394–415. Scopus, doi:10.1287/opre.2014.1322.
Brown DB, Smith JE. Information relaxations, duality, and convex stochastic dynamic programs. Operations Research. 2014 Nov 1;62(6):1394–1415.

Published In

Operations Research

DOI

EISSN

1526-5463

ISSN

0030-364X

Publication Date

November 1, 2014

Volume

62

Issue

6

Start / End Page

1394 / 1415

Related Subject Headings

  • Operations Research
  • 3507 Strategy, management and organisational behaviour
  • 1503 Business and Management
  • 0802 Computation Theory and Mathematics
  • 0102 Applied Mathematics