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

• 成果类型: Article
• 署名作者: Chen, Wei; Dawande, Milind; Janakiraman, Ganesh
• 署名单位: University of Texas System; University of Texas Dallas
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2013.1239
• 发表日期: 2014
• 页码: 81-103
• 关键词: control-models; lost-sales; convex-functions; algorithms; demand; COSTS

摘要

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-\tau-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-\tau-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-\tau-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.