×
Chouman, Mervat; Crainic, Teodor Gabriel; Gendron, Bernard

The impact of filtering in a branch-and-cut algorithm for multicommodity capacitated fixed charge network design. (English) Zbl 1400.90057

EURO J. Comput. Optim. 6, No. 2, 143-184 (2018).
Summary: In this paper, we present a state-of-the-art branch-and-cut (B&C) algorithm for the multicommodity capacitated fixed charge network design problem (MCND). This algorithm combines bounding and branching procedures inspired by the latest developments in mixed-integer programming (MIP) software tools. Several filtering methods that exploit the structure of the MCND are also developed and embedded within the B&C algorithm. These filtering methods apply inference techniques to forbid combinations of values for some variables. This can take the form of adding cuts, reducing the domains of the variables, or fixing the values of the variables. Our experiments on a large set of randomly generated instances show that an appropriate selection of filtering techniques allows the B&C algorithm to perform better than the variant of the algorithm without filtering. These experiments also show that the B&C algorithm, with or without filtering, is competitive with a state-of-the-art MIP solver.

Cited in 7 Documents

MSC:

90B10 Deterministic network models in operations research
90C11 Mixed integer programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut

Keywords:

mixed-integer programming; multicommodity capacitated fixed charge network design; branch-and-cut; filtering

Software:

OOBB
Cite Review PDF
Full Text: DOI
OA License

References:

[1] Aardal, K, Capacitated facility location: separation algorithms and computational experience, Math Program, 81, 149-175, (1998) · Zbl 0919.90096
[2] Aardal, K; Pochet, Y; Wolsey, LA, Capacitated facility location: valid inequalities and facets, Math Oper Res, 20, 562-582, (1995) · Zbl 0846.90088 · doi:10.1287/moor.20.3.562
[3] Achterberg, T; Koch, T; Martin, A, Branching rules revisited, Oper Res Lett, 33, 42-54, (2005) · Zbl 1076.90037 · doi:10.1016/j.orl.2004.04.002
[4] Adenso-Diaz, B; Laguna, M, Fine-tuning of algorithms using fractional experimental designs and local search, Oper Res, 54, 99-114, (2006) · Zbl 1167.90654 · doi:10.1287/opre.1050.0243
[5] Applegate D, Bixby RE, Chvatal V, Cook W (1995) Finding cuts in the TSP. Technical report 95-05, DIMACS technical report
[6] Atamtürk, A, Flow pack facets of the single node fixed-charge flow polytope, Oper Res Lett, 29, 107-114, (2001) · Zbl 1018.90060 · doi:10.1016/S0167-6377(01)00100-6
[7] Atamtürk, A, On capacitated network design cut-set polyhedra, Math Program, 92, 425-437, (2002) · Zbl 1008.90003 · doi:10.1007/s101070100284
[8] Atamtürk, A; Rajan, D, On splittable and unsplittable capacitated network design arc-set polyhedra, Math Program, 92, 315-333, (2002) · Zbl 1008.90003 · doi:10.1007/s101070100284
[9] Atamtürk, A; Savelsbergh, MWP, Integer-programming software systems, Ann Oper Res, 140, 67-124, (2005) · Zbl 1091.90046 · doi:10.1007/s10479-005-3968-2
[10] Balas, E, Facets of the knapsack polytope, Math Program, 8, 146-164, (1975) · Zbl 0316.90046 · doi:10.1007/BF01580440
[11] Barahona, F, Network design using cut inequalities, SIAM J Optim, 6, 823-837, (1996) · Zbl 0856.90112 · doi:10.1137/S1052623494279134
[12] Benichou, M; Gauthier, JM; Girodet, P; Hentges, G; Ribiere, G; Vincent, O, Experiments in mixed-integer programming, Math Program, 1, 76-94, (1971) · Zbl 0233.90016 · doi:10.1007/BF01584074
[13] Bienstock, D; Chopra, S; Günlük, O; Tsai, CY, Minimum cost capacity installation for multicommodity network flows, Math Program, 81, 177-199, (1998) · Zbl 0922.90064
[14] Bienstock, D; Günlük, O, Capacitated network design-polyhedral structure and computation, INFORMS J Comput, 8, 243-259, (1996) · Zbl 0871.90031 · doi:10.1287/ijoc.8.3.243
[15] Chouman, M; Crainic, TG; Gendron, B, Commodity representations and cut-set-based inequalities for multicommodity capacitated fixed charge network design problem, Transp Sci, 51, 650-667, (2017) · doi:10.1287/trsc.2015.0665
[16] Codato, G; Fischetti, M, Combinatorial benders cuts for mixed-integer linear programming, Oper Res, 54, 756-766, (2006) · Zbl 1167.90601 · doi:10.1287/opre.1060.0286
[17] Costa, AM; Cordeau, JF; Gendron, B, Benders, metric and cutset inequalities for multicommodity capacitated network design, Comput Optim Appl, 42, 371-392, (2009) · Zbl 1208.90026 · doi:10.1007/s10589-007-9122-0
[18] Costa, AM; Cordeau, JF; Gendron, B; Laporte, G, Accelerating benders decomposition with heuristic master problem solutions, Pesqui Oper, 32, 3-20, (2012) · Zbl 1255.90083 · doi:10.1590/S0101-74382012005000005
[19] Crainic, TG; Gendreau, M; Farvolden, JM, A simplex-based tabu search method for capacitated network design, INFORMS J Comput, 12, 223-236, (2000) · Zbl 1040.90506 · doi:10.1287/ijoc.12.3.223.12638
[20] Crainic, TG; Frangioni, A; Gendron, B; Soriano, P (ed.); Sanso, B (ed.), Telecommunications network planning, 1-19, (1999), Dordrecht
[21] Crainic, TG; Frangioni, A; Gendron, B, Bundle-based relaxation methods for multicommodity capacitated fixed charge network design, Discrete Appl Math, 112, 73-99, (2001) · Zbl 1026.90010 · doi:10.1016/S0166-218X(00)00310-3
[22] Crainic TG, Frangioni A, Gendron B, Guertin F (2009) OOBB: an object-oriented library for parallel branch-and-bound. In: Presented at the CORS/INFORMS international conference, Toronto, Canada, June 14-17 2009
[23] Crainic, TG; Gendreau, M, Cooperative parallel tabu search for capacitated network design, J Heuristics, 8, 601-627, (2002) · doi:10.1023/A:1020325926188
[24] Crainic, TG; Gendron, B; Hernu, G, A slope scaling/Lagrangean perturbation heuristic with long-term memory for multicommodity capacitated fixed-charge network design, J Heuristics, 10, 525-545, (2004) · Zbl 1062.90009 · doi:10.1023/B:HEUR.0000045323.83583.bd
[25] Frangioni A (2017) http://www.di.unipi.it/ frangio
[26] Gabrel, V; Knippel, A; Minoux, M, Exact solution of multicommodity network optimization problems with general step cost functions, Oper Res Lett, 25, 15-23, (1999) · Zbl 0967.90012 · doi:10.1016/S0167-6377(99)00020-6
[27] Gendron B, Crainic TG (1994) Relaxations for multicommodity capacitated network design problems. Technical report, Publication CRT-945, Centre de recherche sur les transports, Université de Montréal
[28] Gendron, B; Larose, M, Branch-and-price-and-cut for large-scale multicommodity capacitated fixed-charge network design, EURO J Comput Optim, 2, 55-75, (2014) · Zbl 1307.90117 · doi:10.1007/s13675-014-0020-9
[29] Ghamlouche, I; Crainic, TG; Gendreau, M, Cycle-based neighbourhoods for fixed charge capacitated multicommodity network design, Oper Res, 51, 655-667, (2003) · Zbl 1165.90360 · doi:10.1287/opre.51.4.655.16098
[30] Ghamlouche, I; Crainic, TG; Gendreau, M, Path relinking, cycle-based neighbourhoods and capacitated multicommodity network design, Ann Oper Res, 131, 109-133, (2004) · Zbl 1067.90014 · doi:10.1023/B:ANOR.0000039515.90453.1d
[31] Gu, Z; Nemhauser, GL; Savelsbergh, MWP, Lifted cover inequalities for 0-1 integer programs: computation, INFORMS J Comput, 10, 427-437, (1998) · doi:10.1287/ijoc.10.4.427
[32] Gu, Z; Nemhauser, GL; Savelsbergh, MWP, Lifted cover inequalities for 0-1 integer programs: complexity, INFORMS J Comput, 11, 117-123, (1999) · Zbl 1092.90527 · doi:10.1287/ijoc.11.1.117
[33] Gu, Z; Nemhauser, GL; Savelsbergh, MWP, Lifted flow cover inequalities for mixed 0-1 integer programs, Math Program, 85, 439-467, (1999) · Zbl 0977.90030 · doi:10.1007/s101070050067
[34] Günlük, O, A branch-and-cut algorithm for capacitated network design problems, Math Program, 86, 17-39, (1999) · Zbl 1015.90090 · doi:10.1007/s101070050077
[35] Hammer, PL; Johnson, EL; Peled, UN, Facets of regular 0-1 polytopes, Math Program, 8, 179-206, (1975) · Zbl 0314.90064 · doi:10.1007/BF01580442
[36] Hewitt, M; Nemhauser, GL; Savelsbergh, MWP, Combining exact and heuristic approches for the capacitated fixed-charge network flow problem, INFORMS J Comput, 22, 314-325, (2010) · Zbl 1243.90031 · doi:10.1287/ijoc.1090.0348
[37] Holmberg, K; Yuan, D, A Lagrangian heuristic based branch-and-bound approach for the capacitated network design problem, Oper Res, 48, 461-481, (2000) · Zbl 1106.90381 · doi:10.1287/opre.48.3.461.12439
[38] Hooker, JN, Logic, optimization, and constraint programming, INFORMS J Comput, 14, 295-321, (2002) · Zbl 1238.90002 · doi:10.1287/ijoc.14.4.295.2828
[39] Katayama, N; Chen, M; Kubo, M, A capacity scaling heuristic for the multicommodity capacitated network design problem, J Comput Appl Math, 232, 90-101, (2009) · Zbl 1178.90057 · doi:10.1016/j.cam.2008.10.055
[40] Kliewer G, Timajev L (2005) Relax-and-cut for capacitated network design. In Proceedings of algorithms-ESA 2005: 13th annual european symposium on algorithms, pp 47-58. Lecture notes in computer science 3369 · Zbl 1162.90576
[41] Leung, JMY; Magnanti, TL, Valid inequalities and facets of the capacitated plant location problems, Math Program, 44, 271-291, (1989) · Zbl 0686.90021 · doi:10.1007/BF01587093
[42] Louveaux, Q; Wolsey, LA, Lifting, superaddititvity, mixed integer rounding and single node flow sets revisited, Ann Oper Res, 153, 47-77, (2007) · Zbl 1157.90488 · doi:10.1007/s10479-007-0171-7
[43] Magnanti, TL; Mirchandani, PB; Vachani, R, The convex hull of two core capacitated network design problems, Math Program, 60, 233-250, (1993) · Zbl 0788.90071 · doi:10.1007/BF01580612
[44] Magnanti, TL; Mirchandani, PB; Vachani, R, Modeling and solving the two-facility capacitated network loading problem, Oper Res, 43, 142-157, (1995) · Zbl 0830.90051 · doi:10.1287/opre.43.1.142
[45] Martello, S; Toth, P, Upper bounds and algorithms for hard 0-1 knapsack problems, Oper Res, 45, 768-778, (1997) · Zbl 0902.90125 · doi:10.1287/opre.45.5.768
[46] Ortega, F; Wolsey, LA, A branch-and-cut algorithm for the single commodity uncapacitated fixed charge network flow problem, Networks, 41, 143-158, (2003) · Zbl 1106.90016 · doi:10.1002/net.10068
[47] Padberg, MW; Roy, TJ; Wolsey, LA, Valid linear inequalities for fixed charge problems, Oper Res, 33, 842-861, (1985) · Zbl 0579.90072 · doi:10.1287/opre.33.4.842
[48] Raack, C; Koster, AMCA; Orlowski, S; Wessäly, R, On cut-based inequalities for capacitated network design polyhedra, Networks, 57, 141-156, (2011) · Zbl 1207.90023
[49] Rodríguez-Martín, I; Salazar-González, JJ, A local branching heuristic for the capacitated fixed-charge network design problem, Comput Oper Res, 37, 575-581, (2010) · Zbl 1175.90072 · doi:10.1016/j.cor.2008.09.003
[50] Savelsbergh, MWP, Preprocessing and probing techniques for mixed integer programming problems, ORSA J Comput, 6, 445-445, (1994) · Zbl 0814.90093 · doi:10.1287/ijoc.6.4.445
[51] Sellmann M, Kliewer G, Koberstein A (2002) Lagrangian cardinality cuts and variable fixing for capacitated network design. In: Proceedings of algorithms-ESA 2002: 10th annual european symposium on algorithms, pp 845-858. Lecture notes in computer science 2461 · Zbl 1040.90004
[52] Roy, TJ; Wolsey, LA, Solving mixed integer programming problems using automatic reformulation, Oper Res, 35, 45-57, (1987) · Zbl 0614.90082 · doi:10.1287/opre.35.1.45
[53] Wolsey, LA, Faces of linear inequalities in 0-1 variables, Math Program, 8, 165-178, (1975) · Zbl 0314.90063 · doi:10.1007/BF01580441
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.