Mathematics of Operations Research | February 2016
It can be formulated as a stochastic dynamic program but the dynamic program is computationally intractable because of an exponentially large
state space, and a number of heuristics have been proposed to approximate it.
Notable amongst these---both for their revenue performance, as well as their theoretically sound basis---are approximate dynamic programming methods that approximate the value function by basis functions (both affine functions as well as
piecewise-linear functions have been proposed for network RM)
and decomposition methods that relax the constraints of the dynamic program to solve simpler dynamic programs (such as the Lagrangian relaxation methods).
In this paper we show that these two seemingly distinct approaches coincide for the network
RM dynamic program, i.e., the piecewise-linear approximation method and the Lagrangian relaxation method are one and the same.
Sumit Kunnumkal is a Professor and Area Leader of Operations Management at the Indian School of Business (ISB). He holds a PhD in Operations Research from Cornell University. He received his MS in Transportation from the Massachusetts Institute of Technology and a B.Tech in Civil Engineering from the Indian Institute of Technology, Madras.
Professor Kunnumkal has previously taught at the Smith School of Business, Queen’s University, and has held visiting positions at the Singapore University of Technology and Design and Universitat Pompeu Fabra. His research interests lie in the areas of pricing and revenue management, retail operations, assortment planning, and approximate dynamic programming.
At ISB, he has taught in the PGP programme, the Fellow programme, and various Advanced Management and Executive Education programmes.
