Dynamic Programming

A Deterministic Fully Polynomial Time Approximation Scheme For Counting Integer Knapsack Solutions Made Easy

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

    Given $n$ elements with nonnegative integer weights $w=(w_1,\ldots,w_n)$, an integer capacity $C$ and positive integer ranges $u=(u_1,\ldots,u_n)$, we consider the counting version of the classic integer knapsack problem: find the number of distinct multisets whose weights add up to at most $C$. We give a deterministic algorithm that estimates the number of solutions to within … Read more

    The Budgeted Minimum Cost Flow Problem with Unit Upgrading Cost

  • Christina Büsing
  • Arie M.C.A. Koster
  • Sarah Kirchner
  • Annika Thome
    • Categories Combinatorial Optimization, Dynamic Programming, Network Optimization Tags , , ,

    The budgeted minimum cost flow problem (BMCF(K)) with unit upgrading costs extends the classical minimum cost flow problem by allowing to reduce the cost of at most K arcs. In this paper, we consider complexity and algorithms for the special case of an uncapacitated network with just one source. By a reduction from 3-SAT we … Read more

    A Quantitative Comparison of Risk Measures

  • Alois Pichler
    • Categories Applications - OR and Management Sciences, Dynamic Programming, Stochastic Programming Tags ,

    The choice of a risk measure reflects a subjective preference of the decision maker in many managerial, or real world economic problem formulations. To evaluate the impact of personal preferences it is thus of interest to have comparisons with other risk measures at hand. This paper develops a framework for comparing different risk measures. We … Read more

    Nonstationary Direct Policy Search for Risk-Averse Stochastic Optimization

  • Belgacem Bouzaiene-Ayari
  • Somayeh Moazeni
  • Boris Defourny
  • Warren B. Powell
    • Categories Dynamic Programming, Parallel Algorithms, Stochastic Programming Tags , ,

    This paper presents an approach to non-stationary policy search for finite-horizon, discrete-time Markovian decision problems with large state spaces, constrained action sets, and a risk-sensitive optimality criterion. The methodology relies on modeling time variant policy parameters by a non-parametric response surface model for an indirect parametrized policy motivated by the Bellman equation. Through the interpolating … Read more

    Semi-Infinite Relaxations for the Dynamic Knapsack Problem with Stochastic Item Sizes

  • Daniel Blado
  • Weihong Hu
  • Alejandro Toriello
    • Categories 0-1 Programming, Dynamic Programming Tags , ,

    We consider a version of the knapsack problem in which an item size is random and revealed only when the decision maker attempts to insert it. After every successful insertion the decision maker can choose the next item dynamically based on the remaining capacity and available items, while an unsuccessful insertion terminates the process. We … 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

    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