Optimization Online


Fully Polynomial Time (Sigma,Pi)-Approximation Schemes for Continuous Nonlinear Newsvendor and Continuous Stochastic Dynamic Programs

Nir Halman(halman***at***huji.ac.il)
Giacomo Nannicini(giacomo.n***at***gmail.com)

Abstract: We study the continuous newsvendor problem (i.e. a newsvendor problem concerning goods of a non-discrete nature, such as fresh fruit juice) and a class of stochastic dynamic programs with several application areas, such as inventory control of a continuous good, economics, and supply chain management. The class is characterized by continuous state and action spaces, either convex or monotone cost function, and affine transition function. We establish that the newsvendor problem for a continuous good with nonlinear shortage and holding costs, as well as the aforementioned class of stochastic dynamic programs, cannot be approximated to any degree of either relative or additive error, regardless of the scheme used. This is in sharp contrast to the fact that the discrete versions of these problems admit efficient approximations to within any given relative error. To circumvent these hardness results, we introduce the concept of fully polynomial time (Sigma,Pi)-approximation schemes. That is, for every given additive error parameter Sigma>0 and multiplicative error parameter Pi=1+epsilon>1, the scheme returns a feasible solution whose value is at most Sigma + Pi v^*, where v^* >= 0 is the optimal value, and it runs in time polynomial in the input size and in 1/epsilon + log 1/Sigma. We develop fully polynomial time (Sigma,Pi)-approximation schemes for nonlinear newsvendor of a continuous good and for the class of continuous dynamic programs under consideration, allowing a compact and natural representation of the input, i.e., value oracles for the cost and transition functions. In light of our hardness results, such approximation schemes are ``best possible''. Our algorithmic results are achieved by extending to the continuous setting the technique of K-approximation sets and functions introduced by Halman et al. [Math. Oper. Res., 34, (2009), pp. 674--685]. This extension requires a completely new set of analytical and algorithmic tools that may be useful in their own right for further development of approximation algorithms. We perform a preliminary computational evaluation, showing that the proposed approximation scheme is orders of magnitude faster than solving the discretized problem exactly, and finds solutions of better quality than approximate solution approaches taken from the literature for comparable computational effort.

Keywords: Newsvendor problem, stochastic inventory control, hardness of approximation, approximation algorithms, stochastic dynamic programming, K-approximation sets and functions

Category 1: Other Topics (Dynamic Programming )

Category 2: Combinatorial Optimization (Approximation Algorithms )


Download: [PDF]

Entry Submitted: 11/16/2016
Entry Accepted: 11/16/2016
Entry Last Modified: 11/16/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society