benders decomposition

Benders Cut Classification via Support Vector Machines for Solving Two-stage Stochastic Programs

  • Huiwen Jia
  • Siqian Shen
    • Categories Cutting Plane Approaches, Stochastic Programming Tags , , ,

    We consider Benders decomposition for solving two-stage stochastic programs with complete recourse based on finite samples of the uncertain parameters. We define the Benders cuts binding at the final optimal solution or the ones significantly improving bounds over iterations as valuable cuts. We propose a learning-enhanced Benders decomposition (LearnBD) algorithm, which adds a cut classification … Read more

    Avoiding redundant columns by adding classical Benders cuts to column generation subproblems

  • Marco E. Lübbecke
  • Stephen J. Maher
  • Jonas T. Witt
    • Categories (Mixed) Integer Linear Programming Tags , , ,

    When solving the linear programming (LP) relaxation of a mixed-integer program (MIP) with column generation, columns might be generated that are not needed to express any integer optimal solution of the MIP. Such columns are called strongly redundant and the dual bound obtained by solving the LP relaxation is potentially stronger if these columns are … Read more

    Large-scale Influence Maximization via Maximal Covering Location

  • Evren Güney
  • Markus Leitner
  • Mario Ruthmair
  • Markus Sinnl
    • Categories Applications - OR and Management Sciences, Integer Programming, Stochastic Programming Tags , , ,

    Influence maximization aims at identifying a limited set of key individuals in a (social) network which spreads information based on some propagation model and maximizes the number of individuals reached. We show that influence maximization based on the probabilistic independent cascade model can be modeled as a stochastic maximal covering location problem. A reformulation based … Read more

    Enhancing large neighbourhood search heuristics for Benders’ decomposition

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

    A general enhancement of the Benders’ decomposition (BD) 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, few, if any, have been designed for BD. Further, typically the use of large neighbourhood search … Read more

    The SCIP Optimization Suite 6.0

  • Michael Bastubbe
  • Leon Eifler
  • Tristan Gally
  • Gerald Gamrath
  • Ambros Gleixner
  • Robert Lion Gottwald
  • Gregor Hendel
  • Christopher Hojny
  • Thorsten Koch
  • Marco E. Lübbecke
  • Stephen J. Maher
  • Matthias Miltenberger
  • Marc E. Pfetsch
  • Felipe Serrano
  • Matthias Walter
  • Jakob Witzig
  • Benjamin Müller
  • Christian Puchert
  • Daniel Rehfeldt
  • Franziska Schlösser
  • Christoph Schubert
  • Yuji Shinano
  • Merlin Viernickel
  • Fabian Wegscheider
  • Jonas T. Witt
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming Tags , , , , , , , , , , ,

    The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming framework SCIP. This paper discusses enhancements and extensions contained in version 6.0 of the SCIP Optimization Suite. Besides performance improvements of the MIP and MINLP core achieved by new primal heuristics and a new selection criterion … Read more

    Benders Decomposition for Very Large Scale Partial Set Covering and Maximal Covering Problems

  • Jean-François Cordeau
  • Fabio Furini
  • Ivana Ljubić
    • Categories Branch and Cut Algorithms, Combinatorial Optimization Tags , , , ,

    Covering problems constitute an important family of facility location problems. This paper intro- duces a new exact algorithm for two important members of this family: i) the maximal covering location problem, which requires finding a subset of facilities that maximizes the amount of demand covered while respecting a budget constraint on the cost of the … Read more

    Exact and heuristic algorithms for finding envy-free allocations in food rescue pickup and delivery logistics

  • Khaled Almi'ani
  • Divya J Nair
  • David Rey
    • Categories Branch and Cut Algorithms, Production and Logistics, Transportation Tags , , ,

    Food rescue organizations collect and re-distribute surplus perishable food for hunger relief. We propose novel approaches to address this humanitarian logistics challenge and find envy-free allocations of the rescued food together with least travel cost routes. We show that this food rescue and delivery problem is NP-hard and we present a cutting-plane algorithm based on … Read more

    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