Abstract
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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Ahuja R., Orlin J., Sharma D. (2001) Multi-exchange neighborhood search structures for the capacitated minimum spanning tree problem. Math. Program. 91, 71–97
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
Amberg A., Domschke W., Voss S. (1996) Capacitated minimum spanning trees: Algorithms using intelligent search. Comb. Optim. Theory Pract. 1, 9–39
Araque J., Hall L., Magnanti T. (1990) Capacitated trees, capacitated routing, and associated polyhedra. Technical Report OR232-90. MIT, Operations Research Center
Barahona F., Anbil R. (2000) The volume algorithm: producing primal solutions with a subgradient method. Math. Program. 87, 385–399
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
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
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)
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)
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
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
Esau L., Williams K. (1966) On teleprocessing system design part ii: a method for approximating the optimal network. IBM Syst. J. 5, 142–147
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)
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
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
Gavish B. (1983) Formulations and algorithms for the capacitated minimal directed tree problem. J. ACM 30, 118–132
Gouveia L. (1995) A 2n-constraint formulation for the capacitated minimal spanning tree problem. Oper. Res. 43, 130–141
Gouveia L., Hall L. (2002) Multistars and directed flow formulations. Networks 40, 188–201
Gouveia L., Lopes M. (2005) The capacitated minimum spanning tree problem: On improved multistar constraints. Eur. J. Oper. Res. 160, 47–62
Gouveia L., Martins P. (1999) The capacitated minimal spanning tree problem: an experiment with a hop-indexed model. Ann. Oper. Res. 86, 271–294
Gouveia L., Martins P. (2000) A hierarchy of hop-indexed models for the capacitated minimum spanning tree problem. Networks 35, 1–16
Gouveia L., Martins P. (2005) The capacitated minimum spanning tree problem: revisiting hop-indexed formulations. Comput. Oper. Res. 32, 2345–2452
Gouveia L., Saldanha-da-Gama F. (2006) On the capacitated concentrator location problem: a reformulation by discretization. Comput. Oper. Res. 33, 1242–1258
Gzara F., Goffin J.L. (2005) Exact solution of the centralized network design problem on directed graphs. Networks 45, 181–192
Hall L. (1996) Experience with a cutting plane algorithm for the capacitated spanning tree problem. INFORMS J. Comput. 8, 219–234
Hall, L., Magnanti, T.: A polyhedral intersection theorem for capacitated spanning trees. Math. Oper. Res. 17 (1992)
Kim D., Barnhart C., Ware K., Reinhardt G. (1999) Multimodal express package delivery: a service network design application. Transport. Sci. 33, 391–407
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
Letchford A.N., Salazar J.J. (2006) Projection results for vehicle routing. Math. Program. 105, 251–274
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
Lysgaard J., Letchford A., Eglese R. (2004) A new branch-and-cut algorithm for the capacitated vehicle routing problem. Math. Program. 100, 423–445
Malik, K., Yu, G.: A branch and bound algorithm for the capacitated minimum spanning tree problem. Networks 23 (1993)
Martins, P.: Enhanced second order algorithm applied to the capacitated minimum spanning tree problem. Comput. Oper. Res. (2006). (To appear)
Nemhauser G., Wolsey L. (1988) Integer and combinatorial optimization. Wiley, New York
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)
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)
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
Sharaiha Y., Gendreau M., Laporte G., Osman I. (1997) A tabu search algorithm for the capacitated shortest spanning tree problem. Networks 29, 161–171
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
Toth P., Vigo D. (1995) An exact algorithm for the capacitated shortest spanning arborescence. Ann. Oper. Res. 61, 121–141
Van den Akker J., Hurkens C., Savelsbergh M. (2000) Time-indexed formulation for machine scheduling problems: column generation. INFORMS J. Comput. 12, 111–124
Vanderbeck F. (1998) Lot-sizing with start-up times. Manage. Sci. 44, 1409–1425
Weisstein, E.: Farey sequence. From MathWorld–A Wolfram Web Resource (2006). URL: http://mathworld.wolfram.com/FareySequence.html
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Uchoa, E., Fukasawa, R., Lysgaard, J. et al. Robust branch-cut-and-price for the Capacitated Minimum Spanning Tree problem over a large extended formulation. Math. Program. 112, 443–472 (2008). https://doi.org/10.1007/s10107-006-0043-y
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-006-0043-y