INFORMS Open Forum

Read the February 2015 President's Pick from Operations Research for free during February: http://pubsonline.informs.org/stoken/default+domain/PresidentChoice/full/10.1287/opre.2014.1322

Information Relaxations, Duality, and Convex Stochastic Dynamic Programs

David B. Brown, James E. Smith

Operations Research (2014). 62(6):1394-1415. http://dx.doi.org/10.1287/opre.2014.1322

My UC Irvine colleague John Turner suggested this interesting Operations Research article to me; it caught his eye since it provides an example of an airline's network revenue management problem, and it presents clever methods for calculating bounds on optimal solutions of stochastic dynamic programming problems. It captured my attention since it invokes the idea of the value of perfect information from decision analysis to relax the so-called nonanticipativity constraints that a person can't know more about how uncertainties will turn out (such as an uncertain demand for airline seats) than has already been resolved at each decision point.  Imposing penalties that punish violations of the nonanticipativity constraints leads to tighter bounds.  In the network revenue management problem and an inventory management problem (with lost sales and lead times), the authors use these "information relaxation" bounds to show that some relatively simple heuristics are nearly optimal.

-What heuristic methods do you use to find near-optimal solutions in your work?

-How do you know the heuristics are giving you a near-optimal solution?

Abstract: "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."

Subject classifications: dynamic programming; information relaxations; network revenue management; lost-sales inventory models.