Robust branch-cut-and-price for the capacitated minimum spanning tree problem over a large extended formulation. (English) Zbl 1146.90059
Summary: This paper presents a robust branch-cut-and-price algorithm for the Capacitated Minimum Spanning Tree Problem (CMST). The variables are associated to \(q\)-arbs, a structure that arises from a relaxation of the capacitated prize-collecting arborescence problem in order to make it solvable in pseudo-polynomial time. Traditional inequalities over the arc formulation, like Capacity Cuts, are also used. Moreover, a novel feature is introduced in such kind of algorithms: powerful new cuts expressed over a very large set of variables are added, without increasing the complexity of the pricing subproblem or the size of the LPs that are actually solved. Computational results on benchmark instances from the OR-Library show very significant improvements over previous algorithms. Several open instances could be solved to optimality.
MSC:
| 90C27 | Combinatorial optimization |
| 90C57 | Polyhedral combinatorics, branch-and-bound, branch-and-cut |
| 20E28 | Maximal subgroups |
| 20G40 | Linear algebraic groups over finite fields |
| 20C20 | Modular representations and characters |
References:
| [1] | Ahuja R., Orlin J., Sharma D. (2001) Multi-exchange neighborhood search structures for the capacitated minimum spanning tree problem. Math. Program. 91, 71–97 · Zbl 1051.90019 |
| [2] | Ahuja R., Orlin J., Sharma D. (2003) A composite very large-scale neighborhood structure for the capacitated minimum spanning tree problem. Oper. Res. Lett. 31(3): 185–194 · Zbl 1064.90039 · doi:10.1016/S0167-6377(02)00236-5 |
| [3] | Amberg A., Domschke W., Voss S. (1996) Capacitated minimum spanning trees: Algorithms using intelligent search. Comb. Optim. Theory Pract. 1, 9–39 |
| [4] | Araque J., Hall L., Magnanti T. (1990) Capacitated trees, capacitated routing, and associated polyhedra. Technical Report OR232-90. MIT, Operations Research Center |
| [5] | Barahona F., Anbil R. (2000) The volume algorithm: producing primal solutions with a subgradient method. Math. Program. 87, 385–399 · Zbl 0961.90058 · doi:10.1007/s101070050002 |
| [6] | Barnhart C., Hane C., Vance P. (2000) Using branch-and-price-and-cut to solve origin-destination integer multicommodity flow problems. Oper. Res. 40, 318–326 |
| [7] | Barnhart C., Johnson E.L., Nemhauser G.L., Savelsbergh M.W.P., Vance P.H. (1998) Branch-and-price: column generation for solving huge integer programs. Oper. Res. 46, 316–329 · Zbl 0979.90092 · doi:10.1287/opre.46.3.316 |
| [8] | Belov G., Letchford A., Uchoa E.: A node-flow model for 1D stock cutting: Robust branch-cut-and-price. Tech. Rep. RPEP Vol.5 no.7, Universidade Federal Fluminense, Engenharia de Produção, Niterói, Brazil (2005) |
| [9] | Bergson, J.: Uma heurí stica lagrangeana para o problema da árvore geradora capacitada de custo mí nimo. Master’s thesis, Universidade Federal do Rio de Janeiro (2002) |
| [10] | Christofides N., Mingozzi A., Toth P. (1981) Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations. Math. Program. 20, 255–282 · Zbl 0461.90067 · doi:10.1007/BF01589353 |
| [11] | Duhamel, C., Gouveia, L., Moura, P., Souza, M.C.: Models and heuristics for a minimum arborescence problem. Tech. Rep. LIMOS/RR-04-13, Institut Supérieur d’Informatique, de Modélisation et de leurs Applications (2004). URL: http://www.isima.fr/limos/publi/RR-04-13.pdf · Zbl 1175.90059 |
| [12] | Esau L., Williams K. (1966) On teleprocessing system design part ii: a method for approximating the optimal network. IBM Syst. J. 5, 142–147 · doi:10.1147/sj.53.0142 |
| [13] | Felici, G., Gentile, C., Rinaldi, G.: Solving large MIP models in supply chain management by branch & cut. Tech. rep., Istituto di Analisi dei Sistemi ed Informatica del CNR, Italy (2000) |
| [14] | Fukasawa R., Longo H., Lysgaard J., Poggi de Aragão M., Reis M., Uchoa E., Werneck R.F. (2006) Robust branch-and-cut-and-price for the capacitated vehicle routing problem. Math. Program. 106, 491–511 · Zbl 1094.90050 · doi:10.1007/s10107-005-0644-x |
| [15] | Gabow H.N., Galil Z., Spencer T., Tarjan R.E. (1986) Efficient algorithms for finding minimum spanning trees in undirected and directed graphs. Combinatorica 6(2): 109–122 · Zbl 0608.05027 · doi:10.1007/BF02579168 |
| [16] | Gavish B. (1983) Formulations and algorithms for the capacitated minimal directed tree problem. J. ACM 30, 118–132 · Zbl 0504.90052 · doi:10.1145/322358.322367 |
| [17] | Gouveia L. (1995) A 2n-constraint formulation for the capacitated minimal spanning tree problem. Oper. Res. 43, 130–141 · Zbl 0830.90049 · doi:10.1287/opre.43.1.130 |
| [18] | Gouveia L., Hall L. (2002) Multistars and directed flow formulations. Networks 40, 188–201 · Zbl 1035.90097 · doi:10.1002/net.10050 |
| [19] | Gouveia L., Lopes M. (2005) The capacitated minimum spanning tree problem: On improved multistar constraints. Eur. J. Oper. Res. 160, 47–62 · Zbl 1067.90141 · doi:10.1016/j.ejor.2003.10.021 |
| [20] | Gouveia L., Martins P. (1999) The capacitated minimal spanning tree problem: an experiment with a hop-indexed model. Ann. Oper. Res. 86, 271–294 · Zbl 0921.90141 · doi:10.1023/A:1018911003529 |
| [21] | Gouveia L., Martins P. (2000) A hierarchy of hop-indexed models for the capacitated minimum spanning tree problem. Networks 35, 1–16 · Zbl 0938.90067 · doi:10.1002/(SICI)1097-0037(200001)35:1<1::AID-NET1>3.0.CO;2-L |
| [22] | Gouveia L., Martins P. (2005) The capacitated minimum spanning tree problem: revisiting hop-indexed formulations. Comput. Oper. Res. 32, 2345–2452 · Zbl 1066.90102 · doi:10.1016/j.cor.2004.03.011 |
| [23] | Gouveia L., Saldanha-da-Gama F. (2006) On the capacitated concentrator location problem: a reformulation by discretization. Comput. Oper. Res. 33, 1242–1258 · Zbl 1126.90377 · doi:10.1016/j.cor.2004.09.013 |
| [24] | Gzara F., Goffin J.L. (2005) Exact solution of the centralized network design problem on directed graphs. Networks 45, 181–192 · Zbl 1068.90105 · doi:10.1002/net.20061 |
| [25] | Hall L. (1996) Experience with a cutting plane algorithm for the capacitated spanning tree problem. INFORMS J. Comput. 8, 219–234 · Zbl 0871.90032 · doi:10.1287/ijoc.8.3.219 |
| [26] | Hall, L., Magnanti, T.: A polyhedral intersection theorem for capacitated spanning trees. Math. Oper. Res. 17 (1992) · Zbl 0763.90082 |
| [27] | Kim D., Barnhart C., Ware K., Reinhardt G. (1999) Multimodal express package delivery: a service network design application. Transport. Sci. 33, 391–407 · Zbl 0958.90004 · doi:10.1287/trsc.33.4.391 |
| [28] | Kohl N., Desrosiers J., Madsen O., Solomon M., Soumis F. (1999) 2-Path cuts for the vehicle routing problem with time windows. Transport. Sci. 33, 101–116 · Zbl 1004.90015 · doi:10.1287/trsc.33.1.101 |
| [29] | Letchford A.N., Salazar J.J. (2006) Projection results for vehicle routing. Math. Program. 105, 251–274 · Zbl 1085.90032 · doi:10.1007/s10107-005-0652-x |
| [30] | Longo H., Poggi de Aragão M., Uchoa E. (2006) Solving capacitated arc routing problems using a transformation to the CVRP. Comput. Oper. Res. 33, 1823–1837 · Zbl 1087.90054 · doi:10.1016/j.cor.2004.11.020 |
| [31] | Lysgaard J., Letchford A., Eglese R. (2004) A new branch-and-cut algorithm for the capacitated vehicle routing problem. Math. Program. 100, 423–445 · Zbl 1073.90068 · doi:10.1007/s10107-003-0481-8 |
| [32] | Malik, K., Yu, G.: A branch and bound algorithm for the capacitated minimum spanning tree problem. Networks 23 (1993) · Zbl 0793.90090 |
| [33] | Martins, P.: Enhanced second order algorithm applied to the capacitated minimum spanning tree problem. Comput. Oper. Res. (2006). (To appear) |
| [34] | Nemhauser G., Wolsey L. (1988) Integer and combinatorial optimization. Wiley, New York · Zbl 0652.90067 |
| [35] | Pigatti, A., Poggi de Aragão, M., Uchoa, E.: Stabilized branch-and-cut-and-price for the generalized assignment problem. In: Annals of GRACO’05, Electronic Notes in Discrete Mathematics, vol. 19, pp. 389–395 (2005) · Zbl 1203.90137 |
| [36] | Poggi de Aragão, M., Uchoa, E.: Integer program reformulation for robust branch-and-cut-and-price. In: Annals of Mathematical Programming in Rio, pp. 56–61. Búzios, Brazil (2003) |
| [37] | Rolland E., Patterson R., Pirkul H. (1999) Memory adaptive reasoning and greedy assignment techniques for the capacitated minimum spanning tree problem. J. Heuristics 5, 159–180 · Zbl 1071.90581 · doi:10.1023/A:1009629727566 |
| [38] | Sharaiha Y., Gendreau M., Laporte G., Osman I. (1997) A tabu search algorithm for the capacitated shortest spanning tree problem. Networks 29, 161–171 · Zbl 0874.68243 · doi:10.1002/(SICI)1097-0037(199705)29:3<161::AID-NET4>3.0.CO;2-F |
| [39] | Souza M., Duhamel C., Ribeiro C. (2003) A GRASP heuristic for the capacitated minimum spanning tree problem using a memory-based local search strategy. In: Resende M., de Sousa J.(eds) Metaheuristics: Computer decision-making. Kluwer Academic Publishers, Dordrecht, pp. 627–658 |
| [40] | Toth P., Vigo D. (1995) An exact algorithm for the capacitated shortest spanning arborescence. Ann. Oper. Res. 61, 121–141 · Zbl 0844.90104 · doi:10.1007/BF02098285 |
| [41] | Van den Akker J., Hurkens C., Savelsbergh M. (2000) Time-indexed formulation for machine scheduling problems: column generation. INFORMS J. Comput. 12, 111–124 · Zbl 1034.90004 · doi:10.1287/ijoc.12.2.111.11896 |
| [42] | Vanderbeck F. (1998) Lot-sizing with start-up times. Manage. Sci. 44, 1409–1425 · Zbl 0989.90069 · doi:10.1287/mnsc.44.10.1409 |
| [43] | Weisstein, E.: Farey sequence. From MathWorld–A Wolfram Web Resource (2006). URL: http://mathworld.wolfram.com/FareySequence.html |
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.
