Fixed-Dimensional Stochastic Dynamic Programs: An Approximation Scheme and an Inventory Application

DSpace/Manakin Repository

Fixed-Dimensional Stochastic Dynamic Programs: An Approximation Scheme and an Inventory Application

Show full item record

Title: Fixed-Dimensional Stochastic Dynamic Programs: An Approximation Scheme and an Inventory Application
Author(s):
Chen, Wei;
Dawande, Milind;
Janakiraman, Ganesh
Format: text
Item Type: article
Keywords: Show Keywords
Abstract: We study fixed-dimensional stochastic dynamic programs in a discrete setting over a finite horizon. Under the primary assumption that the cost-to-go functions are discrete L♮-convex, we propose a pseudo-polynomial time approximation scheme that solves this problem to within an arbitrary prespecified additive error of ε > 0. The proposed approximation algorithm is a generalization of the explicit-enumeration algorithm and offers us full control in the trade-off between accuracy and running time. The main technique we develop for obtaining our scheme is approximation of a fixed-dimensional L♮-convex function on a bounded rectangular set, using only a selected number of points in its domain. Furthermore, we prove that the approximation function preserves L♮-convexity. Finally, to apply the approximate functions in a dynamic program, we bound the error propagation of the approximation. Our approximation scheme is illustrated on a well-known problem in inventory theory, the single-product problem with lost sales and lead times. We demonstrate the practical value of our scheme by implementing our approximation scheme and the explicit-enumeration algorithm on instances of this inventory problem.
Publisher: INFORMS
ISSN: 0030-364X
Persistent Link: http://dx.doi.org/10.1287/opre.2013.1239
http://hdl.handle.net/10735
Terms of Use: ©2014 INFORMS

Files in this item

Files Size Format View
SOM-FR-GJanakiraman-309484.1.pdf 686.3Kb PDF View/Open

This item appears in the following Collection(s)


Show full item record