benders decomposition

A Benders decomposition method for locating stations in a one-way electric car sharing system under demand uncertainty

  • Hatice Calik
  • Bernard Fortz
    • Categories Branch and Cut Algorithms, Robust Optimization, Transportation Tags , , , , ,

    We focus on a problem of locating recharging stations in one-way station based electric car sharing systems which operate under demand uncertainty. We model this problem as a mixed integer stochastic program and develop a Benders decomposition algorithm based on this formulation. We integrate a stabilization procedure to our algorithm and conduct a large-scale experimental … Read more

    A Branch-and-Benders-Cut Algorithm for the Road Restoration Crew Scheduling and Routing Problem

  • Douglas Alem
  • Pedro Munari
  • Alfredo Moreno
    • Categories Applications - OR and Management Sciences, Branch and Cut Algorithms, Cutting Plane Approaches Tags , , , ,

    Extreme events such as disasters cause partial or total disruption of basic services such as water, energy, communication and transportation. In particular, roads can be damaged or blocked by debris, thereby obstructing access to certain affected areas. Thus, restoration of the damaged roads is necessary to evacuate victims and distribute emergency commodities to relief centers … Read more

    Large neighbourhood Benders’ search

  • Stephen J. Maher
    • Categories (Mixed) Integer Linear Programming, Stochastic Programming Tags , , ,

    A general enhancement of the Benders’ decomposition algorithm can be achieved through the improved use of large neighbourhood search heuristics within mixed-integer programming solvers. While mixed-integer programming solvers are endowed with an array of large neighbourhood search heuristics, their use is typically limited to finding solutions to the Benders’ decomposition master problem, which may be … Read more

    Reliable single allocation hub location problem under hub breakdowns

  • Christoph Buchheim
  • Uwe Clausen
  • Nicolas Kämmerling
  • Borzou Rostami
    • Categories (Mixed) Integer Nonlinear Programming, Branch and Cut Algorithms, Facility Planning and Design Tags , , ,

    The design of hub-and-spoke transport networks is a strategic planning problem, as the choice of hub locations has to remain unchanged for long time periods. However, strikes, disasters or traffic breakdown can lead to the unavailability of a hub for a short period of time. Therefore it is important to consider such events already in … Read more

    A Benders decomposition based framework for solving cable trench problems

  • Hatice Calik
  • Markus Leitner
  • Martin Luipersbeck
    • Categories Integer Programming, Network Optimization Tags , , ,

    In this work, we present an algorithmic framework based on Benders decomposition for the Capacitated p-Cable Trench Problem with Covering. We show that our approach can be applied to most variants of the Cable Trench Problem (CTP) that have been considered in the literature. The proposed algorithm is augmented with a stabilization procedure to accelerate … Read more

    Formulations and Decomposition Methods for the Incomplete Hub Location Problem With and Without Hop-Constraints

  • R.S. Camargo
  • J. F. Campbell
  • Gilberto Miranda
  • M. E. O' Kelly
    • Categories Airline Optimization, Applications - OR and Management Sciences, Transportation Tags , , , ,

    The incomplete hub location problem with and without hop-constraints is modeled using a Leontief substitution system approach. The Leontief formalism provides a set of important theoretical properties and delivers formulations with tight linear bounds that can explicitly incorporate hop constraints for each origin-destination pair of demands. Furthermore, the proposed formulations are amenable to a Benders … Read more

    Combinatorial Benders Cuts for Assembly Line Balancing Problems with Setups

  • Sener Akpinar
  • Tolga Bektas
  • Atabak Elmi
    • Categories Combinatorial Optimization Tags , , , ,

    The classical assembly line balancing problem consists of assigning assembly work to workstations. In the presence of setup times that depend on the sequence of tasks assigned to each workstation, the problem becomes more complicated given that two interdependent problems, namely assignment and sequencing, must be solved simultaneously. The hierarchical nature of these two problems … Read more

    A Benders Decomposition Approach for the Charging Station Location Problem with Plug-in Hybrid Electric Vehicles

  • Okan Arslan
  • Oya Ekin Karasan
    • Categories Cutting Plane Approaches, Facility Planning and Design, Network Optimization Tags , , , , ,

    The flow refueling location problem (FRLP) locates $p$ stations in order to maximize the flow volume that can be accommodated in a road network respecting the range limitations of the vehicles. This paper introduces the charging station location problem with plug-in hybrid electric vehicles (CSLP-PHEV) as a generalization of the FRLP. We consider not only … Read more

    A two-level SDDP Solving Strategy with Risk-Averse multivariate reservoir Storage Levels for Long Term power Generation Planning

  • Andre Diniz
  • Maria Elvira P. Maceira
  • D.D. Penna
  • C. L. Vasconcellos
    • Categories Applications - OR and Management Sciences, Stochastic Programming Tags , ,

    Power generation planning in large-scale hydrothermal systems is a complex optimization task, specially due to the high uncertainty in the inflows to hydro plants. Since it is impossible to traverse the huge scenario tree of the multi-stage problem, stochastic dual dynamic programming (SDDP) is the leading optimization technique to solve it, originally from an expected-cost … Read more

    Efficient approaches for the robust network loading problem

  • Sara Mattia
  • Michael Poss
    • Categories (Mixed) Integer Linear Programming, Network Optimization, Robust Optimization Tags , , , ,

    We consider the Robust Network Loading problem with splittable flows and demands that belong to the budgeted uncertainty set. We compare the optimal solution cost and computational cost of the problem when using static routing, volume routing, affine routing, and dynamic routing. For the first three routing types, we compare the compact formulation with a … Read more