JavaScript is disabled for your browser. Some features of this site may not work without it.
Approximate Dynamic Programming and Stochastic Approximation Methods for Inventory Control and Revenue Management

Author
Kunnumkal, Sumit
Abstract
In this thesis, we develop approximate dynamic programming and stochastic approximation methods for problems in inventory control and revenue management. A unifying feature of the methods we develop is that they exploit the underlying problem structure. By doing so, we are able to
establish certain theoretical properties of our methods, make them more computationally efficient and obtain a faster rate of
convergence.
In the stochastic approximation framework, we develop an algorithm for the monotone estimation problem that uses a projection operator with respect to the max norm onto the order simplex. We show the almost sure convergence of this algorithm and present applications to the Q-learning algorithm and the newsvendor problem with censored demands. Next, we consider a number of inventory control problems for which the so-called base-stock policies are known to be
optimal. We propose stochastic approximation methods to compute the optimal base-stock levels. Existing methods in the literature have only local convergence guarantees. In contrast, we show that the iterates of our methods converge to base-stock levels that are globally optimal. Finally, we consider the revenue management
problem of optimally allocating seats on a single flight leg to
demands from multiple fare classes that arrive sequentially. We
propose a stochastic approximation algorithm to compute the optimal
protection levels. The novel aspect of our method is that it works
with the nonsmooth version of the problem where capacity can only be
allocated in integer quantities. We show that the iterates of our
algorithm converge to the globally optimal protection levels.
In the approximate dynamic programming framework, we use a
Lagrangian relaxation strategy to make the inventory control
decisions in a distribution system consisting of multiple retailers
that face random demand and a warehouse that supplies the retailers.
Our method is based on relaxing the constraints that ensure the
nonnegativity of the shipments to the retailers by associating
Lagrange multipliers to them. We show that our method naturally
provides a lower bound on the optimal objective value. Furthermore,
a good set of Lagrange multipliers can be obtained by
solving a convex optimization problem.
Date Issued
2007-05-23Subject
Approximate dynamic programming; Stochastic approximation; Revenue management; Inventory control
Type
dissertation or thesis