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

Wei Chen (), Milind Dawande () and Ganesh Janakiraman ()
Additional contact information
Wei Chen: Naveen Jindal School of Management, The University of Texas at Dallas, Richardson, Texas 75080
Milind Dawande: Naveen Jindal School of Management, The University of Texas at Dallas, Richardson, Texas 75080
Ganesh Janakiraman: Naveen Jindal School of Management, The University of Texas at Dallas, Richardson, Texas 75080

Operations Research, 2014, vol. 62, issue 1, 81-103

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 (natural) -convex, we propose a pseudo-polynomial time approximation scheme that solves this problem to within an arbitrary prespecified additive error of (epsilon) > 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 (natural) -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 (natural) -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.

Keywords: discrete convexity; multidimensional stochastic dynamic programs; approximation algorithms (search for similar items in EconPapers)
Date: 2014
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2013.1239 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:62:y:2014:i:1:p:81-103

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().