benders decomposition

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

  • Mustafa 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, Energy 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

    Strong Optimal Classification Trees

  • Sina Aghaei
  • Andrés Gómez
  • Phebe Vayanos
    • Categories (Mixed) Integer Linear Programming, Combinatorial Optimization, Statistics Tags , , ,

    Decision trees are among the most popular machine learning models and are used routinely in applications ranging from revenue management and medicine to bioinformatics. In this paper, we consider the problem of learning optimal binary classification trees with univariate splits. Literature on the topic has burgeoned in recent years, motivated both by the empirical suboptimality … Read more

    Efficient presolving methods for the influence maximization problem in social networks

  • Sheng-Jie Chen
  • Wei-Kun Chen
  • Yu-Hong Dai
  • Jian-Hua Yuan
  • Hou-Shan Zhang
    • Categories (Mixed) Integer Linear Programming Tags , , , , ,

    We consider the influence maximization problem (IMP) which asks for identifying a limited number of key individuals to spread influence in a social network such that the expected number of influenced individuals is maximized. The stochastic maximal covering location problem (SMCLP) formulation is a mixed integer programming formulation that effectively approximates the IMP by the … Read more

    A converging Benders’ decomposition algorithm for two-stage mixed-integer recourse models

  • Ward Romeijnders
  • Niels van der Laan
    • Categories (Mixed) Integer Linear Programming, Stochastic Programming Tags , ,

    We propose a new solution method for two-stage mixed-integer recourse models. In contrast to existing approaches, we can handle general mixed-integer variables in both stages, and thus, e.g., do not require that the first-stage variables are binary. Our solution method is a Benders’ decomposition, in which we iteratively construct tighter approximations of the expected second-stage … Read more

    An exact solution approach for an electric bus dispatch problem

  • Matías Alvo
  • Gustavo Angulo
  • Mathias A. Klapp
    • Categories (Mixed) Integer Linear Programming, Scheduling, Transportation Tags , , ,

    We study how to efficiently plan the daily bus dispatch operation within a public transport terminal working with a fleet of electric buses. This requires to formulate and solve a new variant of the Vehicle Scheduling Problem model, in which one has to assign trip itineraries to each vehicle considering that driving ranges are limited, … Read more

    Benders decomposition for Network Design Covering Problems

  • Victor Bucarey
  • Bernard Fortz
  • Martine Labbé
  • Juan A. Mesa
  • Natividad González-Blanco
    • Categories Facility Planning and Design, Transportation Tags , , ,

    We consider two covering variants of the network design problem. We are given a set of origin/destination(O/D) pairs and each such O/D pair is covered if there exists a path in the network from the origin to the destination whose length is not larger than a given threshold. In the first problem, called the maximal … Read more

    A Framework for Generalized Benders’ Decomposition and Its Application to Multilevel Optimization

  • Suresh Bolusani
  • Ted K. Ralphs
    • Categories (Mixed) Integer Linear Programming, Game Theory, Stochastic Programming Tags , , ,

    We describe an algorithmic framework generalizing the well-known framework originally introduced by Benders. We apply this framework to several classes of optimization problems that fall under the broad umbrella of multilevel/multistage mixed integer linear optimization problems. The development of the abstract framework and its application to this broad class of problems provides new insights and … Read more