The Benders decomposition algorithm: a literature review

DOI10.1016/j.ejor.2016.12.005zbMath1402.90158OpenAlexW2560324934WikidataQ115188551 ScholiaQ115188551MaRDI QIDQ1751891

Michel Gendreau, Ragheb Rahmaniani, Teodor Gabriel Crainic, Walter Rei

Publication date: 25 May 2018

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2016.12.005

zbMATH Keywords

combinatorial optimizationBenders decompositionliterature reviewacceleration techniques

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02)

Related Items (only showing first 100 items - show all)

Two heuristic methods based on decomposition to the integrated multi-agent supply chain scheduling and distribution problem ⋮ Solving joint chance constrained problems using regularization and Benders' decomposition ⋮ Implementing Automatic Benders Decomposition in a Modern MIP Solver ⋮ A discussion of probability functions and constraints from a variational perspective ⋮ Stochastic Planning and Scheduling with Logic-Based Benders Decomposition ⋮ A Closest Benders Cut Selection Scheme for Accelerating the Benders Decomposition Algorithm ⋮ Supply–demand hub in industrial clusters: a stochastic approach ⋮ Benders decomposition applied to profit maximizing hub location problem with incomplete hub network ⋮ Model and solution method for mean-risk cost-based post-disruption restoration of interdependent critical infrastructure networks ⋮ A logic-based Benders decomposition method for the multi-trip traveling repairman problem with drones ⋮ Integrated Backup Rolling Stock Allocation and Timetable Rescheduling with Uncertain Time-Variant Passenger Demand Under Disruptive Events ⋮ Scenario cluster Lagrangean decomposition for risk averse in multistage stochastic optimization ⋮ Deterministic electric power infrastructure planning: mixed-integer programming model and nested decomposition algorithm ⋮ Dynamic pooled capacity deployment for urban parcel logistics ⋮ Multi-period green reverse logistics network design: an improved Benders-decomposition-based heuristic approach ⋮ Optimizing rest times and differences in games played: an iterative two-phase approach ⋮ From the separation to the intersection sub-problem in Benders decomposition models with prohibitively-many constraints ⋮ Team Orienteering with Time-Varying Profit ⋮ Solving the Type-2 Assembly Line Balancing with Setups Using Logic-Based Benders Decomposition ⋮ A linear ordering problem of sets ⋮ An accelerated Benders decomposition algorithm for solving a double-type double-standard maximal covering location problem ⋮ Novel Formulations and Logic-Based Benders Decomposition for the Integrated Parallel Machine Scheduling and Location Problem ⋮ Recourse in Kidney Exchange Programs ⋮ Efficient Solution Methods for a General r-Interdiction Median Problem with Fortification ⋮ An effective Benders decomposition algorithm for solving the distributed permutation flowshop scheduling problem ⋮ Decomposition-based algorithms for the crew scheduling and routing problem in road restoration ⋮ Generalized Benders decomposition for competitive facility location with concave demand and zone-specialized variable attractiveness ⋮ Railway disruption management: designing bus bridging services under uncertainty ⋮ Benders decomposition for a period-aggregated resource leveling problem with variable job duration ⋮ Multiple allocation tree of hubs location problem for non-complete networks ⋮ Benders decomposition for network design covering problems ⋮ A Benders decomposition algorithm for demand-driven metro scheduling ⋮ Designing master surgery schedules with downstream unit integration via stochastic programming ⋮ Multi-market portfolio optimization with conditional value at risk ⋮ A Benders decomposition-based approach for logistics service network design ⋮ A scaleable projection-based branch-and-cut algorithm for the \(p\)-center problem ⋮ Affine decision rule approximation to address demand response uncertainty in smart grids' capacity planning ⋮ Logic-based benders decomposition with a partial assignment acceleration technique for avionics scheduling ⋮ Branch-relax-and-check: a tractable decomposition method for order acceptance and identical parallel machine scheduling ⋮ A class of Benders decomposition methods for variational inequalities ⋮ Accelerating Benders decomposition: multiple cuts via multiple solutions ⋮ Benders decomposition and column-and-row generation for solving large-scale linear programs with column-dependent-rows ⋮ Stochastic last mile relief network design with resource reallocation ⋮ A branch-and-Benders-cut algorithm for the crew scheduling and routing problem in road restoration ⋮ Carbon-efficient deployment of electric rubber-tyred gantry cranes in container terminals with workload uncertainty ⋮ Large-scale unit commitment under uncertainty: an updated literature survey ⋮ Logic-Based Benders Decomposition for Large-Scale Optimization ⋮ Accelerating the Benders Decomposition Method: Application to Stochastic Network Design Problems ⋮ Efficient solution selection for two-stage stochastic programs ⋮ Risk and resilience-based optimal post-disruption restoration for critical infrastructures under uncertainty ⋮ Scheduled service network design with resource management for two-tier multimodal city logistics ⋮ Crowdshipping by employees of distribution centers: optimization approaches for matching supply and demand ⋮ Cargo allocation and vessel scheduling on liner shipping with synchronization of transshipments ⋮ Integer programming models for mid-term production planning for high-tech low-volume supply chains ⋮ The determination of optimal treatment plans for volumetric modulated arc therapy (VMAT) ⋮ A study on the optimal inventory allocation for clinical trial supply chains ⋮ A generalized Benders decomposition based algorithm for an inventory location problem with stochastic inventory capacity constraints ⋮ Benders decomposition for the Hazmat transport network design problem ⋮ Optimizing a mineral value chain with market uncertainty using Benders decomposition ⋮ A bi-level programming approach for global investment strategies with financial intermediation ⋮ A Benders' decomposition algorithm with combinatorial cuts for the multi-manned assembly line balancing problem ⋮ Benders decomposition algorithms for two variants of the single allocation hub location problem ⋮ Exact algorithms based on Benders decomposition for multicommodity uncapacitated fixed-charge network design ⋮ A robust disaster preparedness model for effective and fair disaster response ⋮ Exact solution algorithms for the maximum flow problem with additional conflict constraints ⋮ An exact solution method for the TSP with drone based on decomposition ⋮ Exact and heuristic algorithms for the weighted total domination problem ⋮ A time-consistent Benders decomposition method for multistage distributionally robust stochastic optimization with a scenario tree structure ⋮ Large-scale influence maximization via maximal covering location ⋮ Accelerating Benders decomposition for short-term hydropower maintenance scheduling ⋮ Constraint generation for risk averse two-stage stochastic programs ⋮ On single-source capacitated facility location with cost and fairness objectives ⋮ Multi-warehouse package consolidation for split orders in online retailing ⋮ Capacitated multi-period maximal covering location problem with server uncertainty ⋮ Implementing the branch-and-cut approach for a general purpose Benders' decomposition framework ⋮ A combinatorial Benders decomposition algorithm for parallel machine scheduling with working-time restrictions ⋮ Benders decomposition for a stochastic three-level lot sizing and replenishment problem with a distribution structure ⋮ A simulation-based decomposition approach for two-stage staffing optimization in call centers under arrival rate uncertainty ⋮ Branch-and-cut approach based on generalized Benders decomposition for facility location with limited choice rule ⋮ Benders' decomposition for the balancing of assembly lines with stochastic demand ⋮ A robust optimization approach for the multi-mode resource-constrained project scheduling problem ⋮ An accelerated L-shaped method for solving two-stage stochastic programs in disaster management ⋮ Logic-based Benders decomposition algorithm for contamination detection problem in water networks ⋮ Heat and electricity market coordination: a scalable complementarity approach ⋮ Formulations and decomposition methods for the incomplete hub location network design problem with and without hop-constraints ⋮ Mixed-integer linear programming models and algorithms for generation and transmission expansion planning of power systems ⋮ Refined cut selection for Benders decomposition: applied to network capacity expansion problems ⋮ A complementarity model for electric power transmission-distribution coordination under uncertainty ⋮ Benders decomposition for the inventory vehicle routing problem with perishable products and environmental costs ⋮ Logic-based Benders decomposition for scheduling a batching machine ⋮ An adaptive differential evolution with decomposition for photovoltaic parameter extraction ⋮ A framework for generalized Benders' decomposition and its application to multilevel optimization ⋮ Distributionally robust multi-period location-allocation with multiple resources and capacity levels in humanitarian logistics ⋮ Robust alternative fuel refueling station location problem with routing under decision-dependent flow uncertainty ⋮ A Benders decomposition algorithm for the maximum availability service facility location problem ⋮ An L-shaped method with strengthened lift-and-project cuts ⋮ Meta partial Benders decomposition for the logistics service network design problem ⋮ The multiphase course timetabling problem ⋮ Strengthening of feasibility cuts in logic-based benders decomposition ⋮ Logic-based benders decomposition for an inter-modal transportation problem

Cites Work

• Elements of Large-Scale Mathematical Programming Part I: Concepts
• A Modified Linear Program for Columnar Methods in Mathematical Programming
• Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems
• Strengthened Benders Cuts for Stochastic Integer Programs with Continuous Recourse
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Acceleration strategies of Benders decomposition for the security constraints power system expansion planning
• Hub location problems with price sensitive demands
• A cross-decomposition scheme with integrated primal-dual multi-cuts for two-stage stochastic programming investment planning problems
• Decomposition based hybrid metaheuristics
• Accelerating Benders decomposition for closed-loop supply chain network design: case of used durable products with different quality levels
• A branch-and-Benders-cut method for nonlinear power design in green wireless local area networks
• Combinatorial Benders cuts for decomposing IMRT fluence maps using rectangular apertures
• On exact solutions for the minmax regret spanning tree problem
• Decomposition based hybrid VNS-TS algorithm for distributed parallel factories scheduling with virtual corporation
• A combinatorial Benders' decomposition for the lock scheduling problem
• Exact approaches for static data segment allocation problem in an information network
• Accelerating Benders stochastic decomposition for the optimization under uncertainty of the petroleum product supply chain
• A hybrid approach of bundle and Benders applied large mixed linear integer problem
• A hybrid outer-approximation/Benders decomposition algorithm for the single allocation hub location problem under congestion
• A Benders decomposition based heuristic for the hierarchical production planning problem
• A modification of Benders' decomposition algorithm for discrete subproblems: An approach for stochastic programs with integer recourse
• Benders, metric and cutset inequalities for multicommodity capacitated network design
• The integer \(L\)-shaped method for stochastic integer programs with complete recourse
• On the convergence of cross decomposition
• Large-scale mixed integer programming: Benders-type heuristics
• Hydro energy management optimization in a deregulated electricity market
• A hybrid method for the planning and scheduling
• Scheduling and routing of automated guided vehicles: A hybrid approach
• An integrated model for logistics network design
• An integrated aircraft routing, crew scheduling and flight retiming model
• Solving multistage quantified linear optimization problems with the alpha-beta nested Benders decomposition
• Integrated airline scheduling
• Adaptive multicut aggregation for two-stage stochastic linear programs with recourse
• Practical enhancements to the Magnanti-Wong method
• An improved Benders decomposition applied to a multi-layer network design problem
• Improving Benders decomposition using a genetic algorithm
• Partitioning procedures for solving mixed-variables programming problems
• Accelerating the regularized decomposition method for two stage stochastic linear problems
• L-shaped decomposition of two-stage stochastic programs with integer recourse
• Computational assessment of distributed decomposition methods for stochastic linear programs
• Exact solution of multicommodity network optimization problems with general step cost functions
• On using approximations of the Benders master problem
• Robust discrete optimization and its applications
• Scalable parallel Benders decomposition for stochastic linear programming
• Logic-based Benders decomposition
• Bundle-type methods for inexact data
• Benders decomposition and column-and-row generation for solving large-scale linear programs with column-dependent-rows
• Propagating logic-based Benders' decomposition approaches for distributed operating room scheduling
• A survey on Benders decomposition applied to fixed-charge network design problems
• A computational study of Benders decomposition for the integrated aircraft routing and crew scheduling problem
• A demand-shifting feasibility algorithm for Benders decomposition.
• Review of nonlinear mixed-integer and disjunctive programming techniques
• Decomposition algorithms for stochastic programming on a computational grid
• New variants of bundle methods
• An improved Benders decomposition algorithm for the tree of hubs location problem
• Benders decomposition, Lagrangean relaxation and metaheuristic design
• Resolution method for mixed integer bi-level linear problems based on decomposition technique
• Dynamic sequencing and cut consolidation for the parallel hybrid-cut nested L-shaped method
• Application of Benders' decomposition to power plant preventive maintenance scheduling
• A computational study of a solver system for processing two-stage stochastic LPs with enhanced Benders decomposition
• An interior-point Benders based branch-and-cut algorithm for mixed integer programs
• On generating maximal nondominated Benders cuts
• Speed-up Benders decomposition using maximum density cut (MDC) generation
• An improved Benders decomposition algorithm for the logistics facility location problem with capacity expansions
• Solving two-stage stochastic programming problems with level decomposition
• Analysis of backtrack algorithms for listing all vertices and all faces of a convex polyhedron.
• A stochastic programming approach for supply chain network design under uncertainty
• Decomposition with branch-and-cut approaches for two-stage stochastic mixed-integer programming
• Generalized Benders decomposition
• The \(C^3\) theorem and a \(D^2\) algorithm for large scale stochastic mixed-integer programming: set convexification
• Prices stabilization for inexact unit-commitment problems
• A note on the selection of Benders' cuts
• Improving the Integer L-Shaped Method
• Algorithms for Hybrid MILP/CP Models for a Class of Optimization Problems
• Benders Decomposition for Large-Scale Uncapacitated Hub Location
• Accelerating Benders Decomposition by Local Branching
• Combinatorial Benders' Cuts for the Strip Packing Problem
• Combinatorial Benders' Cuts for Mixed-Integer Linear Programming
• Planning and Scheduling by Logic-Based Benders Decomposition
• Benders Decomposition for Production Routing Under Demand Uncertainty
• Accelerating Benders method using covering cut bundle generation
• A nested benders decomposition approach for telecommunication network planning
• Simultaneous Assignment of Locomotives and Cars to Passenger Trains
• Decomposition and Partitioning Methods for Multistage Stochastic Linear Programs
• Tailoring Benders decomposition for uncapacitated network design
• A regularized decomposition method for minimizing a sum of polyhedral functions
• Accelerating Benders Decomposition: Algorithmic Enhancement and Model Selection Criteria
• Solving an Electricity Generating Capacity Expansion Planning Problem by Generalized Benders' Decomposition
• Multicommodity Distribution System Design by Benders Decomposition
• A Modified Benders' Partitioning Algorithm for Mixed Integer Programming
• A Priori Optimization of the Probabilistic Traveling Salesman Problem
• Introduction to Stochastic Programming
• Benders Decomposition for Simultaneous Aircraft Routing and Crew Scheduling
• Inexact Cuts in Benders Decomposition
• Cross decomposition for mixed integer programming
• A Generalized Approach to Dantzig-Wolfe Decomposition for Concave Programs
• Accelerating benders decomposition with heuristicmaster problem solutions
• The Implicit Hitting Set Approach to Solve Combinatorial Optimization Problems with an Application to Multigenome Alignment
• L-Shaped Linear Programs with Applications to Optimal Control and Stochastic Programming

This page was built for publication: The Benders decomposition algorithm: a literature review