Applications – OR and Management Sciences

Strongly Polynomial Primal-Dual Algorithms for Concave Cost Combinatorial Optimization Problems

  • Thomas L. Magnanti
  • Dan Stratila
    • Categories Combinatorial Optimization, Supply Chain Management

    We introduce an algorithm design technique for a class of combinatorial optimization problems with concave costs. This technique yields a strongly polynomial primal-dual algorithm for a concave cost problem whenever such an algorithm exists for the fixed-charge counterpart of the problem. For many practical concave cost problems, the fixed-charge counterpart is a well-studied combinatorial optimization … Read more

    Improved Load Plan Design Through Integer Programming Based Local Search

  • Alan L. Erera
  • Mike Hewitt
  • Martin Savelsbergh
  • Y Zhang
    • Categories (Mixed) Integer Linear Programming, Transportation Tags , ,

    We present integer programming models of the service network design problem faced by less-than-truckload (LTL) freight transportation carriers, and a solution approach for the large-scale instances that result in practical applications. To accurately represent freight consolidation opportunities, the models use a fine discretization of time. Furthermore, the models simultaneously route freight and empty trailers, and … Read more

    A Constructive Proof of the Existence of a Utility in Revealed Preference Theory

  • J-P Crouzeix
  • Andrew C. Eberhard
  • Daniel Ralph
    • Categories Approximation Algorithms, Finance and Economics, Generalized Convexity/Monoticity Tags , ,

    Within the context of the standard model of rationality within economic modelling we show the existence of a utility function that rationalises a demand correspondence, hence completely characterizes the associated preference structure, by taking a dense demand sample. This resolves the problem of revealed preferences under some very mild assumptions on the demand correspondence which … Read more

    Layered Formulation for the Robust Vehicle Routing Problem with Time Windows

  • Agostinho Agra
  • Michael Poss
  • Marielle Christiansen
  • Rosa Figueiredo
  • Lars M. Hvattum
  • Cristina Requejo
    • Categories Integer Programming, Robust Optimization, Transportation Tags , , , ,

    This paper studies the vehicle routing problem with time windows where travel times are uncertain and belong to a predetermined polytope. The objective of the problem is to find a set of routes that services all nodes of the graph and that are feasible for all values of the travel times in the uncertainty polytope. … Read more

    Large Neighborhood Search for LNG Inventory Routing

  • Amr El-bakry
  • Kevin C Furman
  • Vikas Goel
  • Jin-hwa Song
    • Categories Transportation

    Liquefied Natural Gas (LNG) is steadily becoming a common mode for commercializing natural gas. Due to the capital intensive nature of LNG projects, the optimal design of LNG supply chains is extremely important from a profitability perspective. Motivated by the need for a model that can assist in the design analysis of LNG supply chains, … Read more

    Solving multi-stage stochastic mixed integer linear programs by the dual dynamic programming approach

  • Zhihao Cen
    • Categories Applications - OR and Management Sciences, Cutting Plane Approaches, Stochastic Programming

    We consider a model of medium-term commodity contracts management. Randomness takes place only in the prices on which the commodities are exchanged, whilst state variable is multi-dimensional, and decision variable is integer. In our previous article, we proposed an algorithm based on the quantization of random process and a dual dynamic programming type approach to … Read more

    Pricing to accelerate demand learning in dynamic assortment planning for perishable products

  • Natashia Boland
  • Martin Savelsbergh
  • Masoud Talebian
    • Categories Applications - OR and Management Sciences, Marketing Tags , , , ,

    Retailers, from fashion stores to grocery stores, have to decide what range of products to off er, i.e., their product assortment. New business trends, such as mass customization and shorter product life cycles, make predicting demand more difficult, which in turn complicates assortment planning. We propose and study a stochastic dynamic programming model for simultaneously making … Read more

    An Exact Algorithm for Power Grid Interdiction Problem with Line Switching

  • Bo Zeng
  • Long Zhao
    • Categories Applications - OR and Management Sciences, Robust Optimization Tags , , , ,

    Power grid vulnerability analysis is often performed through solving a bi-level optimization problem, which, if solved to optimality, yields the most destructive interdiction plan with the worst loss. As one of the most effective operations to mitigate deliberate outages or attacks, transmission line switching recently has been included and modeled by a binary variable in … Read more

    An Exact Algorithm for Two-stage Robust Optimization with Mixed Integer Recourse Problems

  • Bo Zeng
  • Long Zhao
    • Categories Applications - OR and Management Sciences, Robust Optimization, Scheduling Tags , , ,

    In this paper, we consider a linear two-stage robust optimization model with a mixed integer recourse problem. Currently, this type of two-stage robust optimization model does not have any exact solution algorithm available. We first present a set of sufficient conditions under which the existence of an optimal solution is guaranteed. Then, we present a … Read more

    Risk neutral and risk averse Stochastic Dual Dynamic Programming method

  • Joari Paulo da Costa
  • Alexander Shapiro
  • Murilo Pereira Soares
  • Wajdi Tekaya
    • Categories Dynamic Programming, Scheduling, Stochastic Programming Tags , , , , , ,

    In this paper we discuss risk neutral and risk averse approaches to multistage (linear) stochastic programming problems based on the Stochastic Dual Dynamic Programming (SDDP) method. We give a general description of the algorithm and present computational studies related to planning of the Brazilian interconnected power system. Citation ArticleDownload View PDF