stochastic dynamic programming

On the Out-of-Sample Performance of Stochastic Dynamic Programming and Model Predictive Control

  • Dominic S. T. Keehan
  • Andrew B. Philpott
  • Edward Anderson
    • Categories Dynamic Programming, Stochastic Programming Tags , , ,

    Sample average approximation-based stochastic dynamic programming (SDP) and model predictive control (MPC) are two different methods for approaching multistage stochastic optimization. In this paper we investigate the conditions under which SDP may be outperformed by MPC. We show that, depending on the presence of concavity or convexity, MPC can be interpreted as solving a mean-constrained … Read more

    Index Policies and Performance Bounds for Dynamic Selection Problems

  • David B. Brown
  • James E. Smith
    • Categories Applications - OR and Management Sciences, Dynamic Programming Tags , , , ,

    We consider dynamic selection problems, where a decision maker repeatedly selects a set of items from a larger collection of available items. A classic example is the dynamic assortment problem with demand learning, where a retailer chooses items to offer for sale subject to a display space constraint. The retailer may adjust the assortment over … Read more

    Dynamic Stochastic Approximation for Multi-stage Stochastic Optimization

  • Guanghui Lan
  • Zhiqiang Zhou
    • Categories Convex and Nonsmooth Optimization, Stochastic Programming Tags , ,

    In this paper, we consider multi-stage stochastic optimization problems with convex objectives and conic constraints at each stage. We present a new stochastic first-order method, namely the dynamic stochastic approximation (DSA) algorithm, for solving these types of stochastic optimization problems. We show that DSA can achieve an optimal ${\cal O}(1/\epsilon^4)$ rate of convergence in terms … Read more

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

  • Nir Halman
  • Giacomo Nannicini
    • Categories Approximation Algorithms, Dynamic Programming Tags , , , , ,

    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, … Read more

    Fully Polynomial Time hBcApproximation Schemes for Continuous Stochastic Convex Dynamic Programs

  • Nir Halman
  • Giacomo Nannicini
    • Categories Approximation Algorithms, Dynamic Programming Tags , ,

    We develop fully polynomial time $(\Sigma,\Pi)$-approximation schemes for stochastic dynamic programs with continuous state and action spaces, when the single-period cost functions are convex Lipschitz-continuous functions that are accessed via value oracle calls. That is, for every given additive error parameter $\Sigma>0$ and multiplicative error factor $\Pi=1+\epsilon>1$, the scheme returns a feasible solution whose value … Read more

    Optimal Execution Under Jump Models For Uncertain Price Impact

  • Thomas F. Coleman
  • Yuying Li
  • Somayeh Moazeni
    • Categories Dynamic Programming, Finance and Economics, Stochastic Programming Tags , , ,

    In the execution cost problem, an investor wants to minimize the total expected cost and risk in the execution of a portfolio of risky assets to achieve desired positions. A major source of the execution cost comes from price impacts of both the investor’s own trades and other concurrent institutional trades. Indeed price impact of … Read more

    The optimal harvesting problem under risk aversion

  • Bernardo K. Pagnoncelli
  • Adriana Piazza
    • Categories Applications - OR and Management Sciences, Stochastic Programming Tags , , ,

    We study the exploitation of a one species forest plantation when timber price is uncertain. The work focuses on providing optimality conditions for the optimal harvesting policy in terms of the parameters of the price process and the discount factor. We use risk averse stochastic dynamic programming and use the Conditional Value-at-Risk (CVaR) as our … Read more

    Pricing to accelerate demand learning in dynamic assortment planning for perishable products

  • Natashia Boland
  • Martin Savelsbergh
  • Masoud Talebian
    • Categories Applications - OR and Management Sciences, Marketing Tags , , , ,

    Retailers, from fashion stores to grocery stores, have to decide what range of products to off er, i.e., their product assortment. New business trends, such as mass customization and shorter product life cycles, make predicting demand more difficult, which in turn complicates assortment planning. We propose and study a stochastic dynamic programming model for simultaneously making … Read more

    The optimal harvesting problem with price uncertainty

  • Bernardo K. Pagnoncelli
  • Adriana Piazza
    • Categories Dynamic Programming, Stochastic Programming Tags , , ,

    In this paper we study the exploitation of a one species forest plantation when timber price is governed by a stochastic process. The work focuses on providing closed expressions for the optimal harvesting policy in terms of the parameters of the price process and the discount factor. We assume that harvest is restricted to mature … Read more

    Expected Future Value Decomposition Based Bid Price Generation for Large-Scale Network Revenue Management

  • Laureano F. Escudero
  • Dolores Romero Morales
  • Juan F. Monge
  • Jingbo Wang
    • Categories Stochastic Programming, Yield Management Tags , , , ,

    This paper studies a multi-stage stochastic programming model for large-scale network revenue management. We solve the model by means of the so-called Expected Future Value (EFV) decomposition via scenario analysis, estimating the impact of the decisions made at a given stage on the objective function value related to the future stages. The EFV curves are … Read more