dynamic programming

Convergence of Trajectory Following Dynamic Programming algorithms for multistage stochastic problems without finite support assumptions

  • Maël Forcier
  • Vincent Leclère
    • Categories Dynamic Programming, Stochastic Programming Tags , ,

    We introduce a class of algorithms, called Trajectory Following Dynamic Programming (TFDP) algorithms, that iteratively refines approximation of cost-to-go functions of multistage stochastic problems with independent random variables. This framework encompasses most variants of the Stochastic Dual Dynamic Programming algorithm. Leveraging a Lipschitz assumption on the expected cost-to-go functions, we provide a new convergence and … Read more

    A Route-Based Algorithm for the Electric Vehicle Routing Problem with Multiple Technologies

  • Dario Bezzi
  • Alberto Ceselli
  • Giovanni Righini
    • Categories Applications - OR and Management Sciences Tags , , ,

    Electric vehicles are seen as a pragmatic way of reducing emissions. In freight transportation, they prove to be appealing also in terms of costs, if proper planning algorithms are designed. We consider a variant of the electric vehicle routing problem: a fleet of identical vehicles of limited capacity needs to visit a set of customers … Read more

    Dynamic programming in convex stochastic optimization

  • Teemu Pennanen
  • Ari-Pekka Perkkiö
    • Categories Stochastic Programming Tags , ,

    This paper studies the dynamic programming principle for general convex stochastic optimization problems introduced by Rockafellar and Wets in the 1970s. We extend the applicability of the theory by relaxing compactness and boundedness assumptions. In the context of financial mathematics, the relaxed assumptions are satisfied under the well-known no-arbitrage condition and the reasonable asymptotic elasticity … Read more

    Targeted Multiobjective Dijkstra Algorithm

  • Pedro Maristany de las Casas
  • Luitgard Kraus
  • Antonio Sedeño-Noda
  • Ralf Borndœrfer
    • Categories Multi-Criteria Optimization, Network Optimization Tags , , , , ,

    In this paper, we introduce the Targeted Multiobjective Dijkstra Algorithm (T-MDA), a label setting algorithm for the One-to-One Multiobjective Shortest Path (MOSP) Problem. The T-MDA is based on the recently published Multiobjective Dijkstra Algorithm (MDA) and equips it with A*-like techniques. The resulting speedup is comparable to the speedup that the original A* algorithm achieves … Read more

    Risk-Averse Stochastic Optimal Control: an efficiently computable statistical upper bound

  • Vincent Guigues
  • Alexander Shapiro
  • Yi Cheng
    • Categories Stochastic Programming Tags , , , , ,

    In this paper, we discuss an application of the SDDP type algorithm to nested risk-averse formulations of Stochastic Optimal Control (SOC) problems. We propose a construction of a statistical upper bound for the optimal value of risk-averse SOC problems. This outlines an approach to a solution of a long standing problem in that area of … Read more

    Solving Graph Partitioning on Sparse Graphs: Cuts, Projections, and Extended Formulations

  • Demetrios Papazaharias
  • Jose L. Walteros
    • Categories Combinatorial Optimization, Network Optimization Tags , , , ,

    This paper explores new solution approaches for the graph partitioning problem. While the classic formulations for graph partitioning are compact, they either suffer from a poor relaxation, symmetry, or contain a cubic number of constraints regardless of the graph density. These shortcomings often result in poor branch-and-bound performance. We approach this problem from perspective of … Read more

    Dual SDDP for risk-averse multistage stochastic programs

  • Bernardo Freitas Paulo da Costa
  • Vincent Leclère
    • Categories Dynamic Programming, Stochastic Programming Tags , , , ,

    Risk-averse multistage stochastic programs appear in multiple areas and are challenging to solve. Stochastic Dual Dynamic Programming (SDDP) is a well-known tool to address such problems under time-independence assumptions. We show how to derive a dual formulation for these problems and apply an SDDP algorithm, leading to converging and deterministic upper bounds for risk-averse problems. … Read more

    Central Limit Theorem and Sample Complexity of Stationary Stochastic Programs

  • Yi Cheng
  • Alexander Shapiro
    • Categories Stochastic Programming Tags , , , , , ,

    In this paper we discuss sample complexity of solving stationary stochastic programs by the Sample Average Approximation (SAA) method. We investigate this in the framework of Optimal Control (in discrete time) setting. In particular we derive a Central Limit Theorem type asymptotics for the optimal values of the SAA problems. The main conclusion is that … Read more

    Batch Learning in Stochastic Dual Dynamic Programming

  • Daniel Ávila
  • Nils Löhndorf
  • Anthony Papavasiliou
    • Categories Dynamic Programming, Stochastic Programming Tags , , , ,

    We consider the stochastic dual dynamic programming (SDDP) algorithm, which is a widely employed algorithm applied to multistage stochastic programming, and propose a variant using batch learning, a technique used with success in the reinforcement learning framework. We cast SDDP as a type of Q-learning algorithm and describe its application in both risk neutral and … Read more

    Algorithms for the Clique Problem with Multiple-Choice Constraints under a Series-Parallel Dependency Graph

  • Andreas Bärmann
  • Patrick Gemander
  • Maximilian Merkert
  • Ann-Kathrin Wiertz
  • Francisco Javier Zaragoza Martínez
    • Categories Dynamic Programming, Graphs and Matroids, Polyhedra Tags , , , ,

    The clique problem with multiple-choice constraints (CPMC), i.e. the problem of finding a k-clique in a k-partite graph with known partition, occurs as a substructure in many real-world applications, in particular scheduling and railway timetabling. Although CPMC is NP-complete in general, it is known to be solvable in polynomial time when the so-called dependency graph … Read more