Dynamic Programming

Regularized Stochastic Dual Dynamic Programming for convex nonlinear optimization problems

  • Vincent Guigues
  • Miguel A. Lejeune
  • Wajdi Tekaya
    • Categories Dynamic Programming, Finance and Economics, Stochastic Programming Tags , , , ,

    We define a regularized variant of the Dual Dynamic Programming algorithm called REDDP (REgularized Dual Dynamic Programming) to solve nonlinear dynamic programming equations. We extend the algorithm to solve nonlinear stochastic dynamic programming equations. The corresponding algorithm, called SDDP-REG, can be seen as an extension of a regularization of the Stochastic Dual Dynamic Programming (SDDP) … Read more

    Stochastic Primal-Dual Methods and Sample Complexity of Reinforcement Learning

  • Yichen Chen
  • Mengdi Wang
    • Categories Dynamic Programming Tags ,

    We study the online estimation of the optimal policy of a Markov decision process (MDP). We propose a class of Stochastic Primal-Dual (SPD) methods which exploit the inherent minimax duality of Bellman equations. The SPD methods update a few coordinates of the value and policy estimates as a new state transition is observed. These methods … 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

    Relaxation Analysis for the Dynamic Knapsack Problem with Stochastic Item Sizes

  • Daniel Blado
  • Alejandro Toriello
    • Categories Combinatorial Optimization, 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 dynamically choose the next item based on the remaining capacity and available items, while an unsuccessful insertion terminates the process. We … Read more

    A Copositive Approach for Two-Stage Adjustable Robust Optimization with Uncertain Right-Hand Sides

  • Samuel Burer
  • Guanglin Xu
    • Categories Dynamic Programming, Linear, Cone and Semidefinite Programming, Robust Optimization Tags , , , , ,

    We study two-stage adjustable robust linear programming in which the right-hand sides are uncertain and belong to a convex, compact uncertainty set. This problem is NP-hard, and the affine policy is a popular, tractable approximation. We prove that under standard and simple conditions, the two-stage problem can be reformulated as a copositive optimization problem, which … Read more

    An Effective Dynamic Programming Algorithm for the Minimum-Cost Maximal Knapsack Packing

  • Fabio Furini
  • Ivana Ljubić
  • Markus Sinnl
    • Categories Combinatorial Optimization, Dynamic Programming, Integer Programming

    Given a set of n items with profits and weights and a knapsack capacity C, we study the problem of finding a maximal knapsack packing that minimizes the profit of selected items. We propose for the first time an effective dynamic programming (DP) algorithm which has O(nC) time complexity and O(n+C) space complexity. We demonstrate … Read more

    Stochastic Dual Dynamic Integer Programming

  • Shabbir Ahmed
  • Xu Andy Sun
  • Jikai Zou
    • Categories Dynamic Programming, Integer Programming, Stochastic Programming Tags , , ,

    Multistage stochastic integer programming (MSIP) combines the difficulty of uncertainty, dynamics, and non-convexity, and constitutes a class of extremely challenging problems. A common formulation for these problems is a dynamic programming formulation involving nested cost-to-go functions. In the linear setting, the cost-to-go functions are convex polyhedral, and decomposition algorithms, such as nested Benders’ decomposition and … Read more

    MIDAS: A Mixed Integer Dynamic Approximation Scheme

  • Joseph Frédéric Bonnans
  • Andrew B. Philpott
  • Faisal Wahid
    • Categories Dynamic Programming, Stochastic Programming Tags ,

    Mixed Integer Dynamic Approximation Scheme (MIDAS) is a new sampling-based algorithm for solving finite-horizon stochastic dynamic programs with monotonic Bellman functions. MIDAS approximates these value functions using step functions, leading to stage problems that are mixed integer programs. We provide a general description of MIDAS, and prove its almost-sure convergence to an epsilon-optimal policy when … Read more

    A Polyhedral Approach to Online Bipartite Matching

  • Shabbir Ahmed
  • Alejandro Toriello
  • Alfredo Torrico
    • Categories Dynamic Programming, Polyhedra Tags , ,

    We study the i.i.d. online bipartite matching problem, a dynamic version of the classical model where one side of the bipartition is fixed and known in advance, while nodes from the other side appear one at a time as i.i.d. realizations of a uniform distribution, and must immediately be matched or discarded. We consider various … Read more

    A joint routing and speed optimization problem

  • Ricardo Fukasawa
  • Qie He
  • Fernando Santos
  • Yongjia Song
    • Categories (Mixed) Integer Nonlinear Programming, Dynamic Programming, Transportation

    Fuel cost contributes to a significant portion of operating cost in cargo transportation. Though classic routing models usually treat fuel cost as input data, fuel consumption heavily depends on the travel speed, which has led to the study of optimizing speeds over a given fixed route. In this paper, we propose a joint routing and … Read more