×

Modeling hop-constrained and diameter-constrained minimum spanning tree problems as Steiner tree problems over layered graphs. (English) Zbl 1218.90201

Summary: The hop-constrained minimum spanning tree problem (HMSTP) is an NP-hard problem arising in the design of centralized telecommunication networks with quality of service constraints. We show that the HMSTP is equivalent to a Steiner tree problem (STP) in an appropriate layered graph. We prove that the directed cut model for the STP defined in the layered graph, dominates the best previously known models for the HMSTP. We also show that the Steiner directed cuts in the extended layered graph space can be viewed as being a stronger version of some previously known HMSTP cuts in the original design space. Moreover, we show that these strengthened cuts can be combined and projected into new families of cuts, including facet defining ones, in the original design space. We also adapt the proposed approach to the diameter-constrained minimum spanning tree problem (DMSTP). Computational results with a branch-and-cut algorithm show that the proposed method is significantly better than previously known methods on both problems.

MSC:

90C35 Programming involving graphs or networks
90C11 Mixed integer programming
90C27 Combinatorial optimization
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut

Software:

SteinLib
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Achuthan N.R., Caccetta L., Caccetta P.A., Geelen J.F.: Computational methods for the diameter restricted minimum weight spanning tree problem. Australas. J. Comb. 10, 51–71 (1994) · Zbl 0819.90114
[2] Chopra S., Rao M.R.: The Steiner tree problem I: formulations, compositions and extension of facets. Math. Program. 64(2), 209–229 (1994) · Zbl 0821.90124 · doi:10.1007/BF01582573
[3] Dahl G.: The 2-hop spanning tree problem. Oper. Res. Lett. 23, 21–26 (1998) · Zbl 0957.90093 · doi:10.1016/S0167-6377(98)00029-7
[4] Dahl G.: Notes on polyhedra associated with hop-constrained paths. Oper. Res. Lett. 25, 97–100 (1999) · Zbl 0973.90065 · doi:10.1016/S0167-6377(99)00025-5
[5] Dahl, G., Flatberg, T., Foldnes, N., Gouveia, L.: The jump formulation for the hop-constrained minimum spanning tree problem. Tech. Rep. CIO 5, University of Lisbon (2004)
[6] Dahl G., Gouveia L., Requejo C.: On formulations and methods for the hop-constrained minimum spanning tree problem. In: Pardalos, P., Resende, M. (eds) Handbook of Optimization in Telecommunications., pp. 493–515. Springer, Berlin (2006) · Zbl 1118.90051
[7] Garey M.R., Johnson D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York (1979) · Zbl 0411.68039
[8] Gouveia L.: Using the Miller–Tucker–Zemlin constraints to formulate a minimal spanning tree problem with hop constraints. Comput. Oper. Res. 22(9), 959–970 (1995) · Zbl 0854.90139 · doi:10.1016/0305-0548(94)00074-I
[9] Gouveia L.: Multicommodity flow models for spanning trees with hop constraints. Eur. J. Oper. Res. 95(1), 178–190 (1996) · Zbl 0947.90513 · doi:10.1016/0377-2217(95)00090-9
[10] Gouveia L.: Using variable redefinition for computing lower bounds for minimum spanning and Steiner trees with hop constraints. INFORMS J. Comput. 10(2), 180–188 (1998) · Zbl 1054.90622 · doi:10.1287/ijoc.10.2.180
[11] Gouveia L., Magnanti T.L.: Network flow models for designing diameter-constrained minimum- spanning and Steiner trees. Networks 41(3), 159–173 (2003) · Zbl 1106.90014 · doi:10.1002/net.10069
[12] Gouveia L., Magnanti T.L., Requejo C.: A 2-path approach for odd-diameter-constrained minimum spanning and Steiner trees. Networks 44(4), 254–265 (2004) · Zbl 1058.90069 · doi:10.1002/net.20034
[13] Gouveia L., Magnanti T.L., Requejo C.: An intersecting tree model for odd-diameter-constrained minimum spanning and Steiner trees. Ann. Oper. Res. 146, 19–39 (2006) · Zbl 1107.90007 · doi:10.1007/s10479-006-0049-0
[14] Gouveia L., Requejo C.: A new Lagrangian relaxation approach for the hop-constrained minimum spanning tree problem. Eur. J. Oper. Res. 132(3), 539–552 (2001) · Zbl 1055.90084 · doi:10.1016/S0377-2217(00)00143-0
[15] Gouveia, L., Simonetti, L., Uchoa, E.: Modelling hop-constrained and diameter-constrained minimum spanning tree problems as Steiner tree problems over layered graphs. Tech. Rep. RPEP, vol. 8, no.7, Universidade Federal Fluminense, Engenharia de Produção, Niterói, Brazil (2008) · Zbl 1218.90201
[16] Gruber, M., Raidl, G.R.: A new 0-1 ILP approach for the bounded diameter minimum spanning tree problem. In: Proceedings of the 2nd International Network Optimization Conference, Lisbon, pp. 178–185 (2005)
[17] Hwang F., Richards D., Winter P.: The Steiner Tree Problems. Annals of Discrete Mathematics. North-Holland, Amsterdam (1992) · Zbl 0774.05001
[18] Kerivin H., Mahjoub A.R.: Design of survivable networks: a survey. Networks 46(1), 1–21 (2005) · Zbl 1072.90003 · doi:10.1002/net.20072
[19] Koch T., Martin A.: Solving Steiner tree problems in graphs to optimality. Networks 33, 207–232 (1998) · Zbl 1002.90078 · doi:10.1002/(SICI)1097-0037(199810)32:3<207::AID-NET5>3.0.CO;2-O
[20] Maculan N.: The Steiner problem in graphs. Ann. Discret. Math. 31, 185–212 (1987) · Zbl 0622.90029
[21] Magnanti T.L., Wolsey L.A.: Optimal trees. In: \(\sim\)Ball, M. , Magnanti, T.L. , Monma, C., Nemhauser, G. (eds) Network Models, Handbook in Operations Research and Management Science, vol. 7, pp. 503–615. Elsevier, Amsterdam (1995) · Zbl 0839.90135
[22] Manyem, P., Stallmann, M.F.M.: Some approximation results in multicasting. Tech. Rep. TR-96-03, North Carolina State University (1996)
[23] Noronha, T.F., Santos, A.C., Ribeiro, C.C.: Constraint programming for the diameter constrained minimum spanning tree problem. In: Proceedings of IV Latin-American Algorithms, Graphs and Optimization Symposium, Electronic Notes in Discrete Mathematics, vol. 30, pp. 93–98. Puerto Varas, Chile (2008) · Zbl 1341.05027
[24] Oliveira, C., Pardalos, P., Resende, M.: Optimization problems in multicast tree construction. In: Handbook of Optimization in Telecommunications, pp. 701–731. Springer, Berlin (2006) · Zbl 1118.90024
[25] Poggide Aragão M., Uchoa E., Werneck R.: Dual heuristics on the exact solution of large Steiner problems. Electron. Notes Discret. Math. 7, 150–153 (2001) · Zbl 0983.68010 · doi:10.1016/S1571-0653(04)00247-1
[26] Ribeiro C., Uchoa E., Werneck R.: A hybrid GRASP with perturbations for the Steiner problem in graphs. INFORMS J. Comput. 14, 228–246 (2002) · Zbl 1238.90117 · doi:10.1287/ijoc.14.3.228.116
[27] Santos, A.C., Lucena, A., Ribeiro, C.C.: Solving diameter constrained minimum spanning tree problems in dense graphs. In: Experimental and Efficient Algorithms, Lecture Notes in Computer Science, vol. 3059/2004, pp. 458–467. Springer, Berlin (2004)
[28] Takahashi H., Matsuyama A.: An approximate solution for the Steiner problem in graphs. Mathematica Japonica 24, 573–577 (1980) · Zbl 0435.05036
[29] Uchoa, E.: Algoritmos para problemas de Steiner com aplicações em projeto de circuitos VLSI. Ph.D. thesis, Pontifícia Universidade Católica do Rio de Janeiro (2001)
[30] Uchoa E., Fukasawa R., Lysgaard J., Pessoa A., Poggide Aragão M., Andrade D.: Robust branch-cut-and-price for the capacitated minimum spanning tree problem over a large extended formulation. Math. Program. 112(2), 443–472 (2008) · Zbl 1146.90059 · doi:10.1007/s10107-006-0043-y
[31] Werneck, R.: Problema de Steiner em grafos: algoritmos primais, duais e exatos. Master’s thesis, Pontifícia Universidade Católica do Rio de Janeiro (2001)
[32] Wong R.: A dual ascent approach for Steiner tree problems on a directed graph. Math. Program. 28(3), 271–287 (1984) · Zbl 0532.90092 · doi:10.1007/BF02612335
[33] Woolston K.A., Albin S.L.: The design of centralized networks with reliability and availability constraints. Comput. Oper. Res. 15(3), 207–217 (1988) · doi:10.1016/0305-0548(88)90033-0
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.