Dynamic Programming

Computational and Economic Limitations of Dispatch Operations in the Next-Generation Power Grid

  • Audun Botterud
  • Emil M. Constantinescu
  • Victor M. Zavala
  • Jianhui Wang
    • Categories Dynamic Programming, Linear Programming, Production and Logistics Tags , , , , ,

    We study the interactions between computational and economic performance of dispatch operations under highly dynamic environments. In particular, we discuss the need for extending the forecast horizon of the dispatch formulation in order to anticipate steep variations of renewable power and highly elastic loads. We present computational strategies to solve the increasingly larger optimization problems … Read more

    Dynamic Portfolio Optimization with Transaction Costs: Heuristics and Dual Bounds

  • David B. Brown
  • James E. Smith
    • Categories Applications - OR and Management Sciences, Dynamic Programming, Finance and Economics Tags ,

    We consider the problem of dynamic portfolio optimization in a discrete-time, finite-horizon setting. Our general model considers risk aversion, portfolio constraints (e.g., no short positions), return predictability, and transaction costs. This problem is naturally formulated as a stochastic dynamic program. Unfortunately, with non-zero transaction costs, the dimension of the state space is at least as … Read more

    Aircraft landing problems with aircraft classes

  • Dirk Briskorn
  • Raik Stolletz
    • Categories Applications - OR and Management Sciences, Dynamic Programming, Transportation Tags , , , ,

    This paper focuses on the aircraft landing problem that is to assign landing times to aircraft approaching the airport under consideration. Each aircraft’s landing time must be in a time interval encompassing a target landing time. If the actual landing time deviates from the target landing time additional costs occur which depend on the amount … Read more

    Robust Markov Decision Processes

  • Daniel Kuhn
  • Berc Rustem
  • Wolfram Wiesemann
    • Categories Dynamic Programming, Robust Optimization

    Markov decision processes (MDPs) are powerful tools for decision making in uncertain dynamic environments. However, the solutions of MDPs are of limited practical use due to their sensitivity to distributional model parameters, which are typically unknown and have to be estimated by the decision maker. To counter the detrimental effects of estimation errors, we consider … Read more

    Risk-Averse Dynamic Programming for Markov Decision Processes

  • Andrzej Ruszczyński
    • Categories Dynamic Programming, Stochastic Programming Tags , , , ,

    We introduce the concept of a Markov risk measure and we use it to formulate risk-averse control problems for two Markov decision models: a finite horizon model and a discounted infinite horizon model. For both models we derive risk-averse dynamic programming equations and a value iteration method. For the infinite horizon problem we also develop … Read more

    Decomposition of large-scale stochastic optimal control problems

  • Kengy Barty
  • Pierre Carpentier
  • Pierre Girardeau
    • Categories Dynamic Programming, Stochastic Programming Tags , ,

    In this paper, we present an Uzawa-based heuristic that is adapted to some type of stochastic optimal control problems. More precisely, we consider dynamical systems that can be divided into small-scale independent subsystems, though linked through a static almost sure coupling constraint at each time step. This type of problem is common in production/portfolio management … Read more

    Risk averse feasible policies for large-scale multistage stochastic linear programs

  • Vincent Guigues
  • Claudia Sagastizábal
    • Categories Convex Optimization, Dynamic Programming, Stochastic Programming

    We consider risk-averse formulations of stochastic linear programs having a structure that is common in real-life applications. Specifically, the optimization problem corresponds to controlling over a certain horizon a system whose dynamics is given by a transition equation depending affinely on an interstage dependent stochastic process. We put in place a rolling-horizon time consistent policy. … Read more

    Optimal Geometric Partitions, Covers and K-Centers

  • Romulus Andreica
  • Cristina Teodora Andreica
  • Mugurel Ionut Andreica
  • Eliana-Dina Tirsa
  • Mihai Aristotel Ungureanu
    • Categories Combinatorial Optimization, Dynamic Programming, Facility Planning and Design Tags , , , , ,

    In this paper we present some new, practical, geometric optimization techniques for computing polygon partitions, 1D and 2D point, interval, square and rectangle covers, as well as 1D and 2D interval and rectangle K-centers. All the techniques we present have immediate applications to several cost optimization and facility location problems which are quite common in … Read more

    Locating Restricted Facilities on Binary Maps

  • Cristina Teodora Andreica
  • Madalina Ecaterina Andreica
  • Mugurel Ionut Andreica
    • Categories Dynamic Programming, Facility Planning and Design, Other Topics Tags , , , ,

    In this paper we consider several facility location problems with applications to cost and social welfare optimization, when the area map is encoded as a binary (0,1) mxn matrix. We present algorithmic solutions for all the problems. Some cases are too particular to be used in practical situations, but they are at least a starting … Read more

    Inferring Company Structure from Limited Available Information

  • Romulus Andreica
  • Mugurel Ionut Andreica
    • Categories Dynamic Programming, Finance and Economics, Other Topics Tags , , ,

    In this paper we present several algorithmic techniques for inferring the structure of a company when only a limited amount of information is available. We consider problems with two types of inputs: the number of pairs of employees with a given property and restricted information about the hierarchical structure of the company. We provide dynamic … Read more