benders decomposition

Leveraging Decision Diagrams to Solve Two-stage Stochastic Programs with Binary Recourse and Logical Linking Constraints

  • Moira MacNeil
  • Merve Bodur
    • Categories Stochastic Programming Tags , , ,

    Two-stage stochastic programs with binary recourse are challenging to solve and efficient solution methods for such problems have been limited. In this work, we generalize an existing binary decision diagram-based (BDD-based) approach of Lozano and Smith (Math. Program., 2018) to solve a special class of two-stage stochastic programs with binary recourse. In this setting, the … Read more

    Planning of Container Crossdocking for an Express Shipment Service Network

  • Anton J. Kleywegt
  • Haotian Wu
    • Categories Applications - OR and Management Sciences, Stochastic Programming, Transportation Tags , , , ,

    In air transportation, container crossdocking refers to a loaded container that is transferred at an airport from an incoming flight to an outgoing flight without handling the freight on the container. It reduces handling time and handling cost relative to unloading the container and sorting the freight, and is an economical alternative if a sufficient … Read more

    Exact Solutions to a Carsharing Pricing and Relocation Problem under Uncertainty

  • Giovanni Pantuso
    • Categories Stochastic Programming, Transportation Tags , ,

    In this article we study the problem of jointly deciding carsharing prices and vehicle relocations. We consider carsharing services operating in the context of multi-modal urban transportation systems. Pricing decisions take into account the availability of alternative transport modes, and customer preferences with respect to these. In order to account for the inherent uncertainty in … Read more

    Hub Network Design Problem with Capacity, Congestion and Stochastic Demand Considerations

  • Vedat Bayram
  • Barış Yıldız
  • M. Saleh Farham
    • Categories Second-Order Cone Programming, Stochastic Programming, Transportation Tags , , , , , , ,

    We introduce the hub network design problem with congestion, capacity, and stochastic demand considerations (HNDC), which generalizes the classical hub location problem in several directions. In particular, we extend state-of-the-art by integrating capacity acquisition decision and congestion cost effect into the problem and allowing dynamic routing for origin-destination pairs. Connecting strategic and operational level decisions, … Read more

    Adaptive robust optimization with discrete uncertainty

  • Henri Lefebvre
  • Enrico Malaguti
  • Michele Monaci
    • Categories Robust Optimization Tags , , ,

    In this paper, we study adaptive robust optimization problems with discrete uncertainty. We first show that an adaptive robust counterpart of the multiple knapsack problem includes $\Sigma_2^P$-hard problems. Then, we theoretically prove the validity of a non-trivial reformulation of this class of problems which can be solved by an enumerative algorithm akin to a Branch-and-Benders-cut … Read more

    Determining locations and layouts for parcel lockers to support supply chain viability at the last mile

  • Michael Kahr
    • Categories (Mixed) Integer Linear Programming, Facility Planning and Design, Transportation Tags , , , ,

    The pandemic caused by the corona virus SARS-CoV-2 raised many new challenges for humanity. For instance, governments imposed regulations such as lockdowns, resulting in supply chain shocks at different tiers. Additionally, delivery services reached their capacity limits because the demand for mail orders soared temporarily during the lockdowns. We argue that one option to support … Read more

    The value of stochastic crowd resources and strategic location of mini-depots for last-mile delivery: A Benders decomposition approach

  • Pirmin Fontaine
  • Stefan Minner
  • Santiago Nieto-Isaza
    • Categories Applications - OR and Management Sciences, Supply Chain Management, Transportation Tags , , ,

    Crowd-shipping is an emergent solution to avoid the negative effects caused by the growing demand for last-mile delivery services. Previous research has studied crowd-shipping typically at an operational planning level. However, the study of support infrastructure within a city logistics framework has been neglected, especially from a strategic perspective. We investigate a crowd-sourced last-mile parcel … Read more

    The Stochastic Pseudo-Star Degree Centrality Problem

  • M. Can Camur
  • Thomas C. Sharkey
  • Chrysafis Vogiatzis
    • Categories Combinatorial Optimization, Integer Programming Tags , , ,

    We introduce the stochastic pseudo-star degree centrality problem, which focuses on a novel probabilistic group-based centrality metric. The goal is to identify a feasible induced pseudo-star, which is defined as a collection of nodes forming a star network with a certain probability, such that it maximizes the sum of the individual probabilities of unique assignments … Read more

    A tailored Benders decomposition approach for last-mile delivery with autonomous robots

  • Laurent Alfandari
  • Ivana Ljubić
  • Marcos de Melo da Silva
    • Categories Branch and Cut Algorithms, Network Optimization, Transportation Tags , , ,

    This work addresses an operational problem of a logistics service provider that consists of finding an optimal route for a vehicle carrying customer parcels from a central depot to selected facilities, from where autonomous devices like robots are launched to perform last-mile deliveries. The objective is to minimize a tardiness indicator based on the customer … Read more

    On the Structure of Decision Diagram-Representable Mixed Integer Programs with Application to Unit Commitment

  • Hosseinali Salemi
  • Danial Davarnia
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Smart Grids Tags , , ,

    Over the past decade, decision diagrams (DDs) have been used to model and solve integer programming and combinatorial optimization problems. Despite successful performance of DDs in solving various discrete optimization problems, their extension to model mixed integer programs (MIPs) such as those appearing in energy applications has been lacking. More broadly, the question on which … Read more