dynamic programming

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

    A Dynamic Programming Framework for Combinatorial Optimization Problems on Graphs with Bounded Pathwidth

  • Mugurel Ionut Andreica
    • Categories Dynamic Programming, Graphs and Matroids, Network Optimization Tags , , , ,

    In this paper we present an algorithmic framework for solving a class of combinatorial optimization problems on graphs with bounded pathwidth. The problems are NP-hard in general, but solvable in linear time on this type of graphs. The problems are relevant for assessing network reliability and improving the network’s performance and fault tolerance. The main … Read more

    Information Relaxations and Duality in Stochastic Dynamic Programs

  • David B. Brown
  • Peng Sun
  • James E. Smith
    • Categories Dynamic Programming Tags

    We describe a dual approach to stochastic dynamic programming: we relax the constraint that the chosen policy must be temporally feasible and impose a penalty that punishes violations of temporal feasibility. We describe the theory underlying this dual approach and demonstrate its use in dynamic programming models related to inventory control, option pricing, and oil … Read more

    New solution approaches to the general single machine earliness-tardiness problem

  • Yunpeng Pan
  • Hoksung Yau
  • Leyuan Shi
    • Categories Dynamic Programming, Production and Logistics, Scheduling Tags , , ,

    This paper addresses the general single-machine earliness-tardiness problem with distinct release dates, due dates, and unit costs. The aim of this research is to obtain an exact nonpreemptive solution in which machine idle time is allowed. In a hybrid approach, we formulate and then solve the problem using dynamic programming (DP) while incorporating techniques from … Read more