Zetina, Carlos Armando, Contreras, Ivan ORCID: https://orcid.org/0000000202358108 and Cordeau, JeanFrançois (2019) Exact Algorithms based on Benders Decomposition for Multicommmodity Uncapacitated Fixedcharge Network Design. Computers & Operations Research . ISSN 03050548 (In Press)
Text (In press, accepted manuscript) (application/pdf)
991kBExactAlgorithmsbasedonBendersDecompositionforMul_2019_ComputersOpe.pdf  Accepted Version Restricted to Repository staff only until 12 July 2022. Available under License Creative Commons Attribution Noncommercial No Derivatives. 
Official URL: http://dx.doi.org/10.1016/j.cor.2019.07.007
Abstract
This paper presents two exact algorithms based on Benders decomposition for solving the multicommodity uncapacitated fixedcharge network design problem. The first is a branchandcut algorithm based on a Benders reformulation enhanced with an intree matheuristic to obtain improved feasible solutions, valid inequalities in the projected master problem space to close the linear programming gap, and a tailored core point selection criterion from which significant time savings are obtained. The second exact algorithm exploits the problem’s structure to combine a cutandsolve strategy with Benders decomposition. Extensive computational experiments show both exact algorithms provide a speedup of up to three orders of magnitude compared to a stateoftheart generalpurpose MIP solver’s branchandcut and blackbox Benders decomposition algorithms.
Divisions:  Concordia University > Gina Cody School of Engineering and Computer Science > Mechanical, Industrial and Aerospace Engineering 

Item Type:  Article 
Refereed:  Yes 
Authors:  Zetina, Carlos Armando and Contreras, Ivan and Cordeau, JeanFrançois 
Journal or Publication:  Computers & Operations Research 
Date:  12 July 2019 
Funders: 

Digital Object Identifier (DOI):  10.1016/j.cor.2019.07.007 
Keywords:  Benders decomposition; liftandproject; local branching; matheuristics 
ID Code:  985588 
Deposited By:  MONIQUE LANE 
Deposited On:  23 Jul 2019 18:57 
Last Modified:  23 Jul 2019 18:57 
References:
Y. Adulyasak, J.F. Cordeau, R. Jans Benders decomposition for production routing under demand uncertainty Operations Research, 63 (4) (2015), pp. 851867R.K. Ahuja, T.L. Magnanti, J.B. Orlin Network Flows: Theory, Algorithms, and Applications PrenticeHall, New Jersey, U.S.A. (1993)
J. Andersen, T.G. Crainic, M. Christiansen Service network design with management and coordination of multiple fleets European Journal of Operational Research, 193 (2) (2009), pp. 377389
A. Balakrishnan, T.L. Magnanti, R.T. Wong A dualascent procedure for largescale uncapacitated network design Operations Research, 37 (5) (1989), pp. 716740
N. Balakrishnan, R.T. Wong A network model for the rotating workforce scheduling problem Networks, 20 (1) (1990), pp. 2542
E. Balas Disjunctive programming Annals of Discrete Mathematics, 5 (1979), pp. 351
E. Balas, S. Ceria, G. Cornuéjols A liftandproject cutting plane algorithm for mixed 0–1 programs Mathematical Programming, 58 (1) (1993), pp. 295324
E. Balas, S. Ceria, G. Cornuéjols Mixed 0–1 programming by liftandproject in a branchandcut framework Management Science, 42 (9) (1996), pp. 12291246
E. Balas, M. Perregaard Liftandproject for mixed 0–1 programming: recent progress Discrete Applied Mathematics, 123 (1) (2002), pp. 129154
J.J. Bartholdi, J.B. Orlin, H.D. Ratliff Cyclic scheduling via integer programs with circular ones Operations Research, 28 (5) (1980), pp. 10741085
J.F. Benders Partitioning procedures for solving mixedvariables programming problems. Numerische Mathematik, 4 (1962), pp. 238252
J. Billheimer, P. Gray Network design with fixed and variable cost elements Transportation Science, 7 (1) (1973), pp. 4974
M. Bodur, S. Dash, O. Günlük, J. Luedtke Strengthened Benders cuts for stochastic integer programs with continuous recourse INFORMS Journal on Computing, 29 (1) (2017), pp. 7791
M. Bodur, J.R. Luedtke Mixedinteger rounding enhanced Benders decomposition for multiclass servicesystem staffing and scheduling with arrival rate uncertainty Management Science, 63 (7) (2017), pp. 20732091
T. Boffey, A. Hinxman Solving the optimal network problem
European Journal of Operational Research, 3 (5) (1979), pp. 386393
P. Bonami On optimizing over liftandproject closures Mathematical Programming Computation, 4 (2) (2012), pp. 151179
Q. Botton, B. Fortz, L. Gouveia, M. Poss Benders decomposition for the hopconstrained survivable network design problem INFORMS Journal on Computing, 25 (1) (2013), pp. 1326
H. Calik, M. Leitner, M. Luipersbeck A benders decomposition based framework for solving cable trench problems Computers & Operations Research, 81 (2017), pp. 128140
R.S. de Camargo, G. Miranda, H.P. Luna Benders decomposition for the uncapacitated multiple allocation hub location problem
Computers and Operations Research, 35 (4) (2008), pp. 10471064
S. Climer, W. Zhang Cutandsolve: An iterative search strategy for combinatorial optimization problems Artificial Intelligence, 170 (8) (2006), pp. 714738
I. Contreras, J.F. Cordeau, G. Laporte Benders decomposition for largescale uncapacitated hub location Operations Research, 59 (6) (2011), pp. 14771490
I. Contreras, J.A. Díaz, E. Fernández Lagrangean relaxation for the capacitated hub location problem with single assignment
OR Spectrum, 31 (3) (2009), pp. 483505
J.F. Cordeau, F. Pasin, M.M. Solomon An integrated model for logistics network design Annals of Operations Research, 144 (1) (2006), pp. 5982
J.F. Cordeau, G. Stojković, F. Soumis, J.Desrosiers Benders decomposition for simultaneous aircraft routing and crew scheduling Transportation Science, 35 (4) (2001), pp. 375388
A.M. Costa A survey on Benders decomposition applied to fixedcharge network design problems Computers & Operations Research, 32 (6) (2005), pp. 14291450
A.M. Costa, J.F. Cordeau, B. Gendron Benders, metric and cutset inequalities for multicommodity capacitated network design
Computational Optimization and Applications, 42 (3) (2009), pp. 371392
T.G. Crainic Service network design in freight transportation
European Journal of Operational Research, 122 (2) (2000), pp. 272288
T.G. Crainic, A. Frangioni, B. Gendron Bundlebased relaxation methods for multicommodity capacitated fixed charge network design
Discrete Applied Mathematics, 112 (13) (2001), pp. 7399
T.G. Crainic, J.M. Rousseau Multicommodity, multimode freight transportation: A general modeling and algorithmic framework for the service network design problem Transportation Research Part B: Methodological, 20 (3) (1986), pp. 225242
R. Dionne, M. Florian Exact and approximate algorithms for optimal network design Networks, 9 (1) (1979), pp. 3759
E.D. Dolan, J.J. Moré Benchmarking optimization software with performance profiles Mathematical Programming, 91 (2) (2002), pp. 201213
J. Edmonds, R.M. Karp Theoretical improvements in algorithmic efficiency for network flow problems Journal of the Association for Computing Machinery, 19 (2) (1972), pp. 248264
M. Fischetti, I. Ljubić, M. Sinnl Redesigning Benders decomposition for largescale facility location Management Science, 63 (7) (2017), pp. 21462162
M. Fischetti, I. Ljubić, M. Sinnl Benders decomposition without separability: A computational study for capacitated facility location problems European Journal of Operational Research, 253 (3) (2016), pp. 557569
M. Fischetti, A. Lodi Local branching Mathematical Programming, 98 (13) (2003), pp. 2347
M. Fischetti, D. Salvagnin, A. Zanette A note on the selection of Benders cuts Mathematical Programming, 124 (12) (2010), pp. 175182
P. Fontaine, S. Minner Benders decomposition for the hazmat transport network design problem European Journal of Operational Research, 267 (3) (2018), pp. 9961002
B. Fortz, M. Poss An improved Benders decomposition applied to a multilayer network design problem Operations Research Letters, 37 (5) (2009), pp. 359364
I. Fragkos, J.F. Cordeau, R. Jans The MultiPeriod MultiCommodity Network Design Problem Technical Report, Université de Montréal (2017)
S.L. Gadegaard, A. Klose, L.R. Nielsen An improved cutandsolve algorithm for the singlesource capacitated facility location problem
EURO Journal on Computational Optimization, 6 (1) (2018), pp. 127
A.M. Geoffrion, G.W. Graves Multicommodity distribution system design by Benders decomposition Management Science, 26 (8) (1974), pp. 855856
L. Gouveia, M. JoyceMoniz, M. Leitner Branchandcut methods for the network design problem with vulnerability constraints
Computers & Operations Research, 91 (2018), pp. 190208
F. Gzara, E. Erkut Telecommunications network design with multiple technologies Telecommunication Systems, 46 (2) (2011), pp. 149161
M. Hewitt, G.L. Nemhauser, M.W.P. Savelsbergh Combining exact and heuristic approaches for the capacitated fixedcharge network flow problem INFORMS Journal on Computing, 22 (2) (2010), pp. 314325
K. Holmberg, J. Hellstrand Solving the uncapacitated network design problem by a Lagrangean heuristic and branchandbound
Operations Research, 46 (2) (1998), pp. 247259
M. Jeihoonian, M.K. Zanjani, M. Gendreau Accelerating Benders decomposition for closedloop supply chain network design: Case of used durable products with different quality levels European Journal of Operational Research, 251 (3) (2016), pp. 830845
D.S. Johnson, J.K. Lenstra, A.H.G.R. Kan The complexity of the network design problem Networks, 8 (4) (1978), pp. 279285
E. Keyvanshokooh, S.M. Ryan, E. Kabir Hybrid robust and stochastic optimization for closedloop supply chain network design using accelerated Benders decomposition European Journal of Operational Research, 249 (1) (2016), pp. 7692
J. Kratica, D. Tošić, V. Filipović, I. Ljubić A genetic algorithm for the uncapacitated network design problem Roy R., Köppen M., Ovaska S., Furuhashi T., Hoffmann F. (Eds.), Soft Computing and Industry: Recent Applications, Springer London, London (2002), pp. 329336
B.W. Lamar, Y. Sheffi, W.B. Powell A capacity improvement lower bound for fixed charge network design problems Operations Research, 38 (4) (1990), pp. 704710
C. Lee, K. Lee, S. Park Benders decomposition approach for the robust network design problem with flow bifurcations Networks, 62 (1) (2013), pp. 116
M. Los, C. Lardinois Combinatorial programming, statistical optimization and the optimal transportation network problem
Transportation Research Part B: Methodological, 16 (2) (1982), pp. 89124
T. Magnanti, P. Mireault, R. Wong Tailoring Benders decomposition for uncapacitated network design Gallo G., Sandi C. (Eds.), Network Flow at Pisa (1986), pp. 112154
T.L. Magnanti, R.T. Wong Accelerating Benders decomposition: Algorithmic enhancement and model selection criteria
Operations Research, 29 (3) (1981), pp. 464484
T.L. Magnanti, R.T. Wong Network design and transportation planning: Models and algorithms Transportation Science, 18 (1) (1984), pp. 155
Á.G. Marín, P. Jaramillo Urban rapid transit network design: accelerated benders decomposition Annals of Operations Research, 169 (1) (2009), pp. 3553
M. Minoux Networks synthesis and optimum network design problems: Models, solution methods and applications
Networks, 19 (3) (1989), pp. 313360
J. NaoumSawaya, S. Elhedhli An interiorpoint Benders based branchandcut algorithm for mixed integer programs Annals of Operations Research, 210 (1) (2013), pp. 3355
F. Ortega, L. Wolsey A branchandcut algorithm for the singlecommodity, uncapacitated, fixedcharge network flow problem
Networks, 41 (3) (2003), pp. 143158
C. OrtizAstorquiza, I. Contreras, G. Laporte An exact algorithm for multilevel uncapacitated facility location Transportation Science (2017), pp. 123
M. Padberg, G. Rinaldi A branchandcut algorithm for the resolution of largescale symmetric traveling salesman problems SIAM Review, 33 (1) (1991), pp. 60100
N. Papadakos Practical enhancements to the MagnantiWong method
Operations Research Letters, 36 (4) (2008), pp. 444449
N. Papadakos Integrated airline scheduling Computers & Operations Research, 36 (1) (2009), pp. 176195
R. Rahmaniani, T.G. Crainic, M. Gendreau, W. Rei The Benders decomposition algorithm: A literature review European Journal of Operational Research, 259 (3) (2017), pp. 801817
R. Rahmaniani, T.G. Crainic, M. Gendreau, W. Rei Accelerating the Benders decomposition method: Application to stochastic network design problems SIAM Journal on Optimization, 28 (1) (2018), pp. 875903
C. Randazzo, H. Luna A comparison of optimal methods for local access uncapacitated network design Annals of Operations Research, 106 (14) (2001), pp. 263286
W. Rei, J.F. Cordeau, M. Gendreau, P. Soriano Accelerating Benders decomposition by local branching INFORMS Journal on Computing, 21 (2) (2009), pp. 333345
T. Santoso, S. Ahmed, M. Goetschalckx, A.Shapiro A stochastic programming approach for supply chain network design under uncertainty
European Journal of Operational Research, 167 (1) (2005), pp. 96115
W. van Ackooij, A. Frangioni, W. de Oliveira Inexact stabilized Benders’ decomposition approaches with application to chanceconstrained problems with finite support Computational Optimization and Applications, 65 (3) (2016), pp. 637669
Z. Yang, F. Chu, H. Chen A cutandsolve based algorithm for the singlesource capacitated facility location problem European Journal of Operational Research, 221 (3) (2012), pp. 521532
N. Zarrinpoor, M.S. Fallahnezhad, M.S. Pishvaee The design of a reliable and robust hierarchical health service network using an accelerated Benders decomposition algorithm European Journal of Operational Research, 265 (3) (2018), pp. 10131032
C.A. Zetina, I. Contreras, E. Fernández, C.LunaMota Solving the optimum communication spanning tree problem European Journal of Operational Research, 273 (1) (2019), pp. 108117
Repository Staff Only: item control page