Zetina, Carlos Armando, Contreras, Ivan 
ORCID: https://orcid.org/0000-0002-0235-8108 and Cordeau, Jean-François
(2019)
Exact Algorithms based on Benders Decomposition for Multicommmodity Uncapacitated Fixed-charge Network Design.
Computers & Operations Research
.
ISSN 03050548
(In Press)
Preview |
Text (In press, accepted manuscript) (application/pdf)
991kBExact-Algorithms-based-on-Benders-Decomposition-for-Mul_2019_Computers---Ope.pdf - Accepted Version Available under License Creative Commons Attribution Non-commercial 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 fixed-charge network design problem. The first is a branch-and-cut algorithm based on a Benders reformulation enhanced with an in-tree 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 cut-and-solve strategy with Benders decomposition. Extensive computational experiments show both exact algorithms provide a speed-up of up to three orders of magnitude compared to a state-of-the-art general-purpose MIP solver’s branch-and-cut 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, Jean-Franç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; lift-and-project; local branching; matheuristics |
| ID Code: | 985588 |
| Deposited By: | Monique Lane |
| Deposited On: | 23 Jul 2019 18:57 |
| Last Modified: | 12 Jul 2022 00:00 |
References:
Y. Adulyasak, J.-F. Cordeau, R. Jans Benders decomposition for production routing under demand uncertainty Operations Research, 63 (4) (2015), pp. 851-867R.K. Ahuja, T.L. Magnanti, J.B. Orlin Network Flows: Theory, Algorithms, and Applications Prentice-Hall, 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. 377-389
A. Balakrishnan, T.L. Magnanti, R.T. Wong A dual-ascent procedure for large-scale uncapacitated network design Operations Research, 37 (5) (1989), pp. 716-740
N. Balakrishnan, R.T. Wong A network model for the rotating workforce scheduling problem Networks, 20 (1) (1990), pp. 25-42
E. Balas Disjunctive programming Annals of Discrete Mathematics, 5 (1979), pp. 3-51
E. Balas, S. Ceria, G. Cornuéjols A lift-and-project cutting plane algorithm for mixed 0–1 programs Mathematical Programming, 58 (1) (1993), pp. 295-324
E. Balas, S. Ceria, G. Cornuéjols Mixed 0–1 programming by lift-and-project in a branch-and-cut framework Management Science, 42 (9) (1996), pp. 1229-1246
E. Balas, M. Perregaard Lift-and-project for mixed 0–1 programming: recent progress Discrete Applied Mathematics, 123 (1) (2002), pp. 129-154
J.J. Bartholdi, J.B. Orlin, H.D. Ratliff Cyclic scheduling via integer programs with circular ones Operations Research, 28 (5) (1980), pp. 1074-1085
J.-F. Benders Partitioning procedures for solving mixed-variables programming problems. Numerische Mathematik, 4 (1962), pp. 238-252
J. Billheimer, P. Gray Network design with fixed and variable cost elements Transportation Science, 7 (1) (1973), pp. 49-74
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. 77-91
M. Bodur, J.R. Luedtke Mixed-integer rounding enhanced Benders decomposition for multiclass service-system staffing and scheduling with arrival rate uncertainty Management Science, 63 (7) (2017), pp. 2073-2091
T. Boffey, A. Hinxman Solving the optimal network problem
European Journal of Operational Research, 3 (5) (1979), pp. 386-393
P. Bonami On optimizing over lift-and-project closures Mathematical Programming Computation, 4 (2) (2012), pp. 151-179
Q. Botton, B. Fortz, L. Gouveia, M. Poss Benders decomposition for the hop-constrained survivable network design problem INFORMS Journal on Computing, 25 (1) (2013), pp. 13-26
H. Calik, M. Leitner, M. Luipersbeck A benders decomposition based framework for solving cable trench problems Computers & Operations Research, 81 (2017), pp. 128-140
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. 1047-1064
S. Climer, W. Zhang Cut-and-solve: An iterative search strategy for combinatorial optimization problems Artificial Intelligence, 170 (8) (2006), pp. 714-738
I. Contreras, J.-F. Cordeau, G. Laporte Benders decomposition for large-scale uncapacitated hub location Operations Research, 59 (6) (2011), pp. 1477-1490
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. 483-505
J.-F. Cordeau, F. Pasin, M.M. Solomon An integrated model for logistics network design Annals of Operations Research, 144 (1) (2006), pp. 59-82
J.-F. Cordeau, G. Stojković, F. Soumis, J.Desrosiers Benders decomposition for simultaneous aircraft routing and crew scheduling Transportation Science, 35 (4) (2001), pp. 375-388
A.M. Costa A survey on Benders decomposition applied to fixed-charge network design problems Computers & Operations Research, 32 (6) (2005), pp. 1429-1450
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. 371-392
T.G. Crainic Service network design in freight transportation
European Journal of Operational Research, 122 (2) (2000), pp. 272-288
T.G. Crainic, A. Frangioni, B. Gendron Bundle-based relaxation methods for multicommodity capacitated fixed charge network design
Discrete Applied Mathematics, 112 (1-3) (2001), pp. 73-99
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. 225-242
R. Dionne, M. Florian Exact and approximate algorithms for optimal network design Networks, 9 (1) (1979), pp. 37-59
E.D. Dolan, J.J. Moré Benchmarking optimization software with performance profiles Mathematical Programming, 91 (2) (2002), pp. 201-213
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. 248-264
M. Fischetti, I. Ljubić, M. Sinnl Redesigning Benders decomposition for large-scale facility location Management Science, 63 (7) (2017), pp. 2146-2162
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. 557-569
M. Fischetti, A. Lodi Local branching Mathematical Programming, 98 (1-3) (2003), pp. 23-47
M. Fischetti, D. Salvagnin, A. Zanette A note on the selection of Benders cuts Mathematical Programming, 124 (1-2) (2010), pp. 175-182
P. Fontaine, S. Minner Benders decomposition for the hazmat transport network design problem European Journal of Operational Research, 267 (3) (2018), pp. 996-1002
B. Fortz, M. Poss An improved Benders decomposition applied to a multi-layer network design problem Operations Research Letters, 37 (5) (2009), pp. 359-364
I. Fragkos, J.-F. Cordeau, R. Jans The Multi-Period Multi-Commodity Network Design Problem Technical Report, Université de Montréal (2017)
S.L. Gadegaard, A. Klose, L.R. Nielsen An improved cut-and-solve algorithm for the single-source capacitated facility location problem
EURO Journal on Computational Optimization, 6 (1) (2018), pp. 1-27
A.M. Geoffrion, G.W. Graves Multicommodity distribution system design by Benders decomposition Management Science, 26 (8) (1974), pp. 855-856
L. Gouveia, M. Joyce-Moniz, M. Leitner Branch-and-cut methods for the network design problem with vulnerability constraints
Computers & Operations Research, 91 (2018), pp. 190-208
F. Gzara, E. Erkut Telecommunications network design with multiple technologies Telecommunication Systems, 46 (2) (2011), pp. 149-161
M. Hewitt, G.L. Nemhauser, M.W.P. Savelsbergh Combining exact and heuristic approaches for the capacitated fixed-charge network flow problem INFORMS Journal on Computing, 22 (2) (2010), pp. 314-325
K. Holmberg, J. Hellstrand Solving the uncapacitated network design problem by a Lagrangean heuristic and branch-and-bound
Operations Research, 46 (2) (1998), pp. 247-259
M. Jeihoonian, M.K. Zanjani, M. Gendreau Accelerating Benders decomposition for closed-loop supply chain network design: Case of used durable products with different quality levels European Journal of Operational Research, 251 (3) (2016), pp. 830-845
D.S. Johnson, J.K. Lenstra, A.H.G.R. Kan The complexity of the network design problem Networks, 8 (4) (1978), pp. 279-285
E. Keyvanshokooh, S.M. Ryan, E. Kabir Hybrid robust and stochastic optimization for closed-loop supply chain network design using accelerated Benders decomposition European Journal of Operational Research, 249 (1) (2016), pp. 76-92
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. 329-336
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. 704-710
C. Lee, K. Lee, S. Park Benders decomposition approach for the robust network design problem with flow bifurcations Networks, 62 (1) (2013), pp. 1-16
M. Los, C. Lardinois Combinatorial programming, statistical optimization and the optimal transportation network problem
Transportation Research Part B: Methodological, 16 (2) (1982), pp. 89-124
T. Magnanti, P. Mireault, R. Wong Tailoring Benders decomposition for uncapacitated network design Gallo G., Sandi C. (Eds.), Network Flow at Pisa (1986), pp. 112-154
T.L. Magnanti, R.T. Wong Accelerating Benders decomposition: Algorithmic enhancement and model selection criteria
Operations Research, 29 (3) (1981), pp. 464-484
T.L. Magnanti, R.T. Wong Network design and transportation planning: Models and algorithms Transportation Science, 18 (1) (1984), pp. 1-55
Á.G. Marín, P. Jaramillo Urban rapid transit network design: accelerated benders decomposition Annals of Operations Research, 169 (1) (2009), pp. 35-53
M. Minoux Networks synthesis and optimum network design problems: Models, solution methods and applications
Networks, 19 (3) (1989), pp. 313-360
J. Naoum-Sawaya, S. Elhedhli An interior-point Benders based branch-and-cut algorithm for mixed integer programs Annals of Operations Research, 210 (1) (2013), pp. 33-55
F. Ortega, L. Wolsey A branch-and-cut algorithm for the single-commodity, uncapacitated, fixed-charge network flow problem
Networks, 41 (3) (2003), pp. 143-158
C. Ortiz-Astorquiza, I. Contreras, G. Laporte An exact algorithm for multilevel uncapacitated facility location Transportation Science (2017), pp. 1-23
M. Padberg, G. Rinaldi A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems SIAM Review, 33 (1) (1991), pp. 60-100
N. Papadakos Practical enhancements to the Magnanti-Wong method
Operations Research Letters, 36 (4) (2008), pp. 444-449
N. Papadakos Integrated airline scheduling Computers & Operations Research, 36 (1) (2009), pp. 176-195
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. 801-817
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. 875-903
C. Randazzo, H. Luna A comparison of optimal methods for local access uncapacitated network design Annals of Operations Research, 106 (1-4) (2001), pp. 263-286
W. Rei, J.-F. Cordeau, M. Gendreau, P. Soriano Accelerating Benders decomposition by local branching INFORMS Journal on Computing, 21 (2) (2009), pp. 333-345
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. 96-115
W. van Ackooij, A. Frangioni, W. de Oliveira Inexact stabilized Benders’ decomposition approaches with application to chance-constrained problems with finite support Computational Optimization and Applications, 65 (3) (2016), pp. 637-669
Z. Yang, F. Chu, H. Chen A cut-and-solve based algorithm for the single-source capacitated facility location problem European Journal of Operational Research, 221 (3) (2012), pp. 521-532
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. 1013-1032
C.A. Zetina, I. Contreras, E. Fernández, C.Luna-Mota Solving the optimum communication spanning tree problem European Journal of Operational Research, 273 (1) (2019), pp. 108-117
All items in Spectrum are protected by copyright, with all rights reserved. The use of items is governed by Spectrum's terms of access.
Repository Staff Only: item control page
Download Statistics
Download Statistics