Top

Journal of Combinatorial Optimization

Published in:

29-06-2018

Accelerating benders decomposition: multiple cuts via multiple solutions

Authors: N. Beheshti Asl, S. A. MirHassani

Published in: Journal of Combinatorial Optimization | Issue 3/2019

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Benders decomposition (BD) is a well-known approach that has been successfully applied to various mathematical programming problems. According to previous studies, slow convergence is the main drawback of this method. In this paper, multi-solution of the master problem has been applied to accelerate the BD algorithm and improve both lower and upper bounds by simultaneously adding multiple feasibility and optimality cuts. A novel integration of Benders cuts was used to prevent the growth of master problem. Computational experiments were applied to a series of logistics facility location problems. Our numerical experiments resulted in a 61% decrease in the total number of iterations and up to 73% reduction in the solution time, confirming the outstanding performance of the proposed method.

previous article Operating room planning and surgical case scheduling: a review of literature

next article Pareto optimal equilibria for selfish bin packing with uniform cost sharing

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Adulyasak Y, Cordeau J, Jans R (2015) Benders decomposition for production routing under demand uncertainty. Oper Res 63(4):851–867MathSciNetMATHCrossRef

Behnamian J (2014) Decomposition based hybrid VNS-TS algorithm for distributed parallel factories scheduling with virtual corporation. Comput Oper Res 52:181–191MathSciNetMATHCrossRef

Crainic T, Hewitt M, Rei W (2016) Partial decomposition strategies for two-stage stochastic integer programs. Interuniversity Research Center on Enterprise Network, Logistics and Transportation (CIRRELT), Université du Québec Montréal, Montreal

Emami S, Moslehi G, Sabbagh M (2017) A Benders decomposition approach for order acceptance and scheduling problem: a robust optimization approach. Comput Appl Math 36(4):1471–1515MathSciNetMATHCrossRef

Fábián C, Szőke Z (2007) Solving two-stage stochastic programming problems with level decomposition. CMS 4(4):313–353MathSciNetMATHCrossRef

Fontaine P, Miner S (2014) Benders decomposition for discrete–continuous linear bi level problems with application to traffic network design. Transp Res Part B Methodol 70:163–172CrossRef

Fontaine P, Minner S (2018) Benders decomposition for the hazmat transport network design problem. Eur J Oper Res 267:996–1002MathSciNetMATHCrossRef

Gelareh S, Monemi RN, Nickel S (2015) Multi-period hub location problems in transportation. Transp Res Part E Logist Transp Rev 75:67–94CrossRef

Jenabi M, Ghomi SF, Torabi S, Hosseinian S (2015) Acceleration strategies of Benders decomposition for the security constraints power system expansion planning. Ann Oper Res 235(1):337–369MathSciNetMATHCrossRef

Kochetov Y, Ivanenko D (2005) Computationally difficult instances for the uncapacitated facility location problem. In: Ibaraki T, Nonobe K, Yagiura M (eds) Metaheuristics: progress as real problem solvers. Operations research/computer science interfaces series, vol 32. Springer, Boston, pp 351–367CrossRef

Luong C (2015) An examination of Benders decomposition approaches in large-scale healthcare optimization problems. Master’s thesis, University of Toronto, Toronto

Magnanti T, Wong R (1981) Accelerating Benders decomposition: algorithmic enhancement and model selection criteria. Oper Res 29(3):464–484MathSciNetMATHCrossRef

McDaniel D, Devine M (1977) A modified Benders’ partitioning algorithm for mixed integer programming. Manag Sci 24(3):312–319MATHCrossRef

Naoum-Sawaya J, Elhedhli S (2010) A nested Benders decomposition approach for telecommunication network planning. Naval Res Logist (NRL) 57(6):519–539MathSciNetMATHCrossRef

Naoum-Sawaya J, Elhedhli S (2013) An interior-point Benders based branch-and-cut algorithm for mixed integer programs. Ann Oper Res 210(1):33–55MathSciNetMATHCrossRef

Papadakos N (2008) Practical enhancement to the Magnanti–Wong method. Oper Res Lett 36(4):444–449MathSciNetMATHCrossRef

Poojari C, Beasley J (2009) Improving Benders decomposition using genetic algorithm. Eur J Oper Res 199(1):89–97MathSciNetMATHCrossRef

Rahmaniani R, Crainic T, Gendreau M, Rei W (2017) The Benders decomposition algorithm: a literature review. Eur J Oper Res 259(3):801–817MathSciNetMATHCrossRef

Rubiales A, Lotito P, Parente L (2013) Stabilization of the generalized Benders decomposition applied to short-term hydrothermal coordination problem. IEEE Latin Am Trans 11(5):1212–1224CrossRef

Saharidis G, Ierapetritou M (2010) Improving Benders decomposition using maximum feasible subsystem (MFS) cut generation strategy. Comput Chem Eng 34(8):1237–1245CrossRef

Saharidis G, Ierapetritou M (2013) Speed-up Benders decomposition using maximum density cut (MDC) generation. Ann Oper Res 210(1):101–123MathSciNetMATHCrossRef

Sherali H, Lunday B (2013) On generating maximal nondominated Benders cuts. Ann Oper Res 210(1):57–72MathSciNetMATHCrossRef

Tang L, Jiang W, Saharidis G (2013) An improved Benders decomposition algorithm for the logistics facility location problem with capacity expansions. Ann Oper Res 210(1):165–190MathSciNetMATHCrossRef

Wang Q, McCauley JD, Litvinov E (2016) Solving corrective risk-based security-constrained optimal power flow with Lagrangian relaxation and Benders decomposition. Int J Electr Power Energy Syst 75:255–264CrossRef

Yang Y, Lee J (2012) A tighter cut generation strategy for acceleration of Benders decomposition. Comput Chem Eng 44:84–93CrossRef

Zarandi M (2010) Using decomposition to solve facility location/fleet management problems. Master’s thesis, University of Toronto, Canada

Title: Accelerating benders decomposition: multiple cuts via multiple solutions
Authors: N. Beheshti Asl
S. A. MirHassani
Publication date: 29-06-2018
Publisher: Springer US
Published in: Journal of Combinatorial Optimization / Issue 3/2019
Print ISSN: 1382-6905
Electronic ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-018-0320-8

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 3/2019

A polynomial algorithm determining cyclic vertex connectivity of k-regular graphs with fixed k

Competitive analysis of randomized online strategies for the multi-agent k-Canadian Traveler Problem

Drawer algorithms for 1-space bounded multidimensional hyperbox packing

Client assignment problems for latency minimization

Verifying schedulability of tasks in ROS-based systems

Approximation algorithms for the graph balancing problem with two speeds and two job lengths

Premium Partner