approximate dynamic programming

From Infinite to Finite Programs: Explicit Error Bounds with Applications to Approximate Dynamic Programming

  • Daniel Kuhn
  • Tobias Sutter
  • John Lygeros
  • Peyman Mohajerin Esfahani
    • Categories Dynamic Programming, Infinite Dimensional Optimization, Stochastic Programming Tags , , , ,

    We consider linear programming (LP) problems in infinite dimensional spaces that are in general computationally intractable. Under suitable assumptions, we develop an approximation bridge from the infinite-dimensional LP to tractable finite convex programs in which the performance of the approximation is quantified explicitly. To this end, we adopt the recent developments in two areas of … Read more

    The Dynamic Dispatch Waves Problem for Same-Day Delivery

  • Alan L. Erera
  • Mathias A. Klapp
  • Alejandro Toriello
    • Categories Applications - OR and Management Sciences, Supply Chain Management, Transportation Tags , ,

    We study same-day delivery systems by formulating the Dynamic Dispatch Waves Problem (DDWP), which models a distribution center where geographically located delivery orders realize dynamically throughout the day. At each decision epoch (wave), the system’s operator chooses whether or not to dispatch a vehicle route loaded with orders ready for service, to minimize vehicle travel … Read more

    Approximate Dynamic Programming for a Class of Long-Horizon Maritime Inventory Routing Problems

  • Myun-Seok Cheon
  • George L. Nemhauser
  • Dimitri J. Papageorgiou
  • Joel Sokol
    • Categories Production and Logistics, Supply Chain Management, Transportation Tags , , , ,

    We study a deterministic maritime inventory routing problem with a long planning horizon. For instances with many ports and many vessels, mixed-integer linear programming (MIP) solvers often require hours to produce good solutions even when the planning horizon is 90 or 120 periods. Building on the recent successes of approximate dynamic programming (ADP) for road-based … Read more

    Optimizing Trading Decisions for Hydro Storage Systems using Approximate Dual Dynamic Programming

  • Nils Löhndorf
  • David Wozabal
  • Stefan Minner
    • Categories Applications - OR and Management Sciences, Dynamic Programming, Stochastic Programming Tags , , ,

    We propose a new approach to optimize operations of hydro storage systems with multiple connected reservoirs which participate in wholesale electricity markets. Our formulation integrates short-term intraday with long-term interday decisions. The intraday problem considers bidding decisions as well as storage operation during the day and is formulated as a stochastic program. The interday problem … Read more

    Simulation Optimization for the Stochastic Economic Lot Scheduling Problem

  • Nils Löhndorf
  • Stefan Minner
    • Categories Dynamic Programming, Optimization of Simulated Systems, Scheduling Tags , , , , ,

    We study simulation optimization methods for the stochastic economic lot scheduling problem. In contrast to prior research, we focus on methods that treat this problem as a black box. Based on a large-scale numerical study, we compare approximate dynamic programming with a global search for parameters of simple control policies. We propose two value function … Read more

    Approximate Dynamic Programming with Bezier Curves/Surfaces for Top-percentile traffic routing

  • Andreas Grothey
  • Xinan Yang
    • Categories Dynamic Programming, Telecommunications Tags , , , , ,

    Multi-homing is used by Internet Service Provider (ISP) to connect to the Internet via different network providers. This study investigates the optimal routing strategy under multi-homing in the case where network providers charge ISPs according to top-percentile pricing (i.e. based on the $\theta$-th highest volume of traffic shipped). We call this problem the Top-percentile Traffic … Read more