Dynamic Programming

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

    Provably Near-Optimal Approximation Schemes for Implicit Stochastic and for Sample-Based Dynamic Programs

  • Nir Halman
    • Categories Dynamic Programming Tags , , ,

    In this paper we address two models of non-deterministic discrete-time finite-horizon dynamic programs (DPs): implicit stochastic DPs – the information about the random events is given by value oracles to their CDFs; and sample-based DPs – the information about the random events is deduced via samples. In both models the single period cost functions are … Read more

    A forward-backward-forward differential equation and its asymptotic properties

  • Sebastian Banert
  • Radu Ioan Bot
    • Categories Convex Optimization, Dynamic Programming, Nonsmooth Optimization Tags , , , ,

    In this paper, we approach the problem of finding the zeros of the sum of a maximally monotone operator and a monotone and Lipschitz continuous one in a real Hilbert space via an implicit forward-backward-forward dynamical system with nonconstant relaxation parameters and stepsizes of the resolvents. Besides proving existence and uniqueness of strong global solutions … Read more

    The One-Dimensional Dynamic Dispatch Waves Problem

  • Alan L. Erera
  • Mathias A. Klapp
  • Alejandro Toriello
    • Categories Dynamic Programming, Production and Logistics, Transportation Tags , , ,

    We study same-day delivery (SDD) distribution systems by formulating the Dynamic Dispatch Wave Problem (DDWP), which models a depot where delivery requests arrive dynamically throughout a service day. At any dispatch epoch (wave), the information available to the decision maker is (1) a set of known, open requests which remain unfulfilled, and (2) a set … Read more

    Asymptotic optimality of Tailored Base-Surge policies in dual-sourcing inventory systems

  • David A. Goldberg
  • Linwei Xin
    • Categories Dynamic Programming, Stochastic Programming, Supply Chain Management Tags , , , , ,

    Dual-sourcing inventory systems, in which one supplier is faster (i.e. express) and more costly, while the other is slower (i.e. regular) and cheaper, arise naturally in many real-world supply chains. These systems are notoriously difficult to optimize due to the complex structure of the optimal solution and the curse of dimensionality, having resisted solution for … Read more

    Parameter-free Sampled Fictitious Play for Solving Deterministic Dynamic Programming Problems

  • Irina S Dolinskaya
  • Marina A. Epelman
  • Esra Sisikoglu
  • Robert L. Smith
    • Categories Dynamic Programming, Network Optimization, Transportation Tags , ,

    To facilitate fast solution of deterministic dynamic programming problems, we present a parameter-free variation of the Sampled Fictitious Play (SFP) algorithm. Its random tie-braking procedure imparts a natural randomness to the algorithm which prevents it from “getting stuck” at a local optimal solution and allows the discovery of an optimal path in a finite number … Read more

    Simplex Algorithm for Countable-state Discounted Markov Decision Processes

  • Marina A. Epelman
  • H. Edwin Romeijn
  • Ilbin Lee
  • Robert L. Smith
    • Categories Dynamic Programming, Infinite Dimensional Optimization, Linear Programming Tags , ,

    We consider discounted Markov Decision Processes (MDPs) with countably-infinite state spaces, finite action spaces, and unbounded rewards. Typical examples of such MDPs are inventory management and queueing control problems in which there is no specific limit on the size of inventory or queue. Existing solution methods obtain a sequence of policies that converges to optimality … Read more

    Process-Based Risk Measures for Observable and Partially Observable Discrete-Time Controlled Systems

  • Jingnan Fan
  • Andrzej Ruszczyński
    • Categories Dynamic Programming, Stochastic Programming

    For controlled discrete-time stochastic processes we introduce a new class of dynamic risk measures, which we call process-based. Their main features are that they measure risk of processes that are functions of the history of the base process. We introduce a new concept of conditional stochastic time consistency and we derive the structure of process-based … Read more

    Information Relaxation Bounds for Infinite Horizon Markov Decision Processes

  • David B. Brown
  • Martin Haugh
    • Categories Dynamic Programming, Scheduling, Stochastic Programming Tags , ,

    We consider the information relaxation approach for calculating performance bounds for stochastic dynamic programs (DPs), following Brown, Smith, and Sun (2010). This approach generates performance bounds by solving problems with relaxed nonanticipativity constraints and a penalty that punishes violations of these constraints. In this paper, we study infinite horizon DPs with discounted costs and consider … Read more

    Singularly Perturbed Markov Decision Processes: A Multiresolution Algorithm

  • Chin Pang Ho
  • Panos Parpas
    • Categories Dynamic Programming Tags , , ,

    Singular perturbation techniques allow the derivation of an aggregate model whose solution is asymptotically optimal for Markov Decision Processes with strong and weak interactions. We develop an algorithm that takes advantage of the asymptotic optimality of the aggregate model in order to compute the solution of the original model with theoretically better complexity than conventional … Read more