dynamic programming

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

    Complexity of the Critical Node Problem over trees

  • Marco Di Summa
  • Andrea Grosso
  • Marco Locatelli
    • Categories Graphs and Matroids Tags , , ,

    In this paper we deal with the Critical Node Problem (CNP), i.e., the problem of searching for a given number K of nodes in a graph G, whose removal minimizes the number of connections between pairs of nodes in the residual graph. While the NP-completeness of this problem for general graphs has been already established … Read more

    A Bi-directional Resource-bounded Dynamic Programming Approach for the Traveling Salesman Problem with Time Windows

  • Jing-Quan Li
    • Categories Network Optimization Tags , ,

    This paper presents a bi-directional resource-bounded label setting algorithm for the traveling salesman problem with time windows, in which the objective is to minimize travel times. Label extensions and dominance start simultaneously in both forward and backward directions: the forward direction from the starting depot and the backward direction from the terminating depot. The resultant … Read more

    A Bi-directional Resource-bounded Dynamic Programming Approach for the Traveling Salesman Problem with Time Windows

  • Jing-Quan Li
    • Categories Network Optimization Tags , ,

    This paper presents a bi-directional resource-bounded label setting algorithm for the traveling salesman problem with time windows, in which the objective is to minimize travel times. Label extensions and dominance start simultaneously in both forward and backward directions: the forward direction from the starting depot and the backward direction from the terminating depot. The resultant … 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

    On a time consistency concept in risk averse multi-stage stochastic programming

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

    In this paper we discuss time consistency of multi-stage risk averse stochastic programming problems. We approach the concept of time consistency from an optimization point of view. That is, at each state of the system optimality of a decision policy should not involve states which cannot happen in the future. We also discuss a relation … Read more

    A Linear Storage-Retrieval Policy for Robust Warehouse Management

  • Marcus Ang
  • Melvyn Sim
  • Yun Fong Lim
    • Categories Robust Optimization Tags , ,

    Assigning products to and retrieving them from proper storage locations in a unit-load warehouse are crucial in minimizing its operating cost. The problem becomes intractable when the warehouse faces uncertain demand in a dynamic setting. We assume a factor-based demand model in which demand for each product in each period is affinely dependent on some … 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

    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

    Minimum Dissatisfaction Personnel Scheduling

  • Romulus Andreica
  • Mugurel Ionut Andreica
    • Categories Combinatorial Optimization, Dynamic Programming, Scheduling Tags , , , ,

    In this paper we consider two problems regarding the scheduling of available personnel in order to perform a given quantity of work, which can be arbitrarily decomposed into a sequence of activities. We are interested in schedules which minimize the overall dissatisfaction, where each employee’s dissatisfaction is modeled as a time-dependent linear function. For the … Read more