dynamic programming

Evolutionary Dynamic Optimization: A Survey of the State of the Art

  • Juergen Branke
  • Trung Thanh Nguyen
  • Shengxiang Yang
    • Categories Meta Heuristics, Optimization Software and Modeling Systems, Other Topics Tags , , , ,

    Optimization in dynamic environments is a challenging but important task since many real-world optimization problems are changing over time. Evolutionary computation and swarm intelligence are good tools to address optimization problems in dynamic environments due to their inspiration from natural self-organized systems and biological evolution, which have always been subject to changing environments. Evolutionary optimization … Read more

    Time Consistency Decisions and Temporal Decomposition of Coherent Risk Functionals

  • Georg Ch. Pflug
  • Alois Pichler
    • Categories Convex Optimization, Nonlinear Optimization, Stochastic Programming Tags , ,

    It is well known that most risk measures (risk functionals) are time inconsistent in the following sense: It may happen that today some loss distribution appears to be less risky than another, but looking at the conditional distribution at a later time, the opposite relation holds. In this article we demonstrate that this time inconsistency … Read more

    On the convergence of decomposition methods for multi-stage stochastic convex programs

  • Pierre Girardeau
  • Vincent Leclère
  • Andrew B. Philpott
    • Categories Convex Optimization, Dynamic Programming, Stochastic Programming Tags , , , ,

    We prove the almost-sure convergence of a class of sampling-based nested decomposition algorithms for multistage stochastic convex programs in which the stage costs are general convex functions of the decisions, and uncertainty is modelled by a scenario tree. As special cases, our results imply the almost-sure convergence of SDDP, CUPPS and DOASA when applied to … Read more

    A Dynamic Programming Heuristic for the Quadratic Knapsack Problem

  • Franklin Djeumou Fomeni
  • Adam N. Letchford
    • Categories (Mixed) Integer Nonlinear Programming, Combinatorial Optimization, Dynamic Programming Tags , ,

    It is well known that the standard (linear) knapsack problem can be solved exactly by dynamic programming in O(nc) time, where n is the number of items and c is the capacity of the knapsack. The quadratic knapsack problem, on the other hand, is NP-hard in the strong sense, which makes it unlikely that it … Read more

    Time consistency of dynamic risk measures

  • Alexander Shapiro
    • Categories Dynamic Programming, Stochastic Programming Tags , , , ,

    In this paper we discuss time consistency of risk averse multistage stochastic programming problems. We show, in a framework of finite scenario trees, that composition of law invariant coherent risk measures can be law invariant only for the expectation or max-risk measures. CitationPreprintArticleDownload View PDF

    Time-inconsistent multistage stochastic programs: martingale bounds

  • Georg Ch. Pflug
  • Alois Pichler
    • Categories Dynamic Programming, Stochastic Programming Tags , ,

    Abstract. It is well known that multistage programs, which maximize expectation or expected utility, allow a dynamic programming formulation, and that other objectives destroy the dynamic programming character of the problem. This paper considers a risk measure at the final stage of a multistage stochastic program. Although these problems are not time consistent, it is … Read more

    Optimal Toll Design: A Lower Bound Framework for the Asymmetric Traveling Salesman Problem

  • Alejandro Toriello
    • Categories 0-1 Programming, Combinatorial Optimization, Dynamic Programming Tags , , , ,

    We propose a framework of lower bounds for the asymmetric traveling salesman problem (TSP) based on approximating the dynamic programming formulation with diff erent basis vector sets. We discuss how several well-known TSP lower bounds correspond to intuitive basis vector choices and give an economic interpretation wherein the salesman must pay tolls as he travels between … Read more

    Managing Operational and Financing Decisions to Meet Consumption Targets

  • Lucy Gongtao Chen
  • Zhuoyu Long
  • Melvyn Sim
    • Categories Applications - OR and Management Sciences, Dynamic Programming Tags , , ,

    We study dynamic operational decision problems where risky cash flows are being resolved over a finite planning horizon. Financing decisions via lending and borrowing are available to smooth out consumptions over time with the goal of achieving some prescribed consumption targets. Our target-oriented decision criterion is based on the aggregation of Aumann and Serrano (2008) … Read more

    Removing critical nodes from a graph: complexity results and polynomial algorithms for the case of bounded treewidth

  • Bernardetta Addis
  • Marco Di Summa
  • Andrea Grosso
    • Categories Combinatorial Optimization Tags , , ,

    We consider the problem of deleting a limited number of nodes from a graph in order to minimize a connectivity measure between the surviving nodes. We prove that the problem is $NP$-complete even on quite particular types of graph, and define a dynamic programming recursion that solves the problem in polynomial time when the graph … Read more

    Stochastic programs without duality gaps

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

    This paper studies dynamic stochastic optimization problems parametrized by a random variable. Such problems arise in many applications in operations research and mathematical finance. We give sufficient conditions for the existence of solutions and the absence of a duality gap. Our proof uses extended dynamic programming equations, whose validity is established under new relaxed conditions … Read more