Dynamic Programming Driven Memetic Search for the Steiner Tree Problem with Revenues, Budget, and Hop Constraints

References

• Andonov R, Poirriez V, Rajopadhye S (2000) Unbounded knapsack problem: Dynamic programming revisited. Eur. J. Oper. Res. 123(2):168–181.Crossref, Google Scholar
• Beasley JE (1990) OR-library: Distributing test problems by electronic mail. J. Oper. Res. Soc. 41(11):1069–1072.Crossref, Google Scholar
• Benlic U, Hao JK (2011) A multilevel memetic approach for improving graph k-partitions. IEEE Trans. Evolut. Comput. 15(5): 624–642.Crossref, Google Scholar
• Botton Q, Fortz B, Gouveia L, Poss M (2013) Benders decomposition for the hop-constrained survivable network design problem. INFORMS J. Comput. 25(1):13–26.Link, Google Scholar
• Bui TN, Deng XH, Catherine M (2012) An improved ant-based algorithm for the degree-constrained minimum spanning tree problem. IEEE Trans. Evolut. Comput. 16(2):266–278.Crossref, Google Scholar
• Carvalho PMS, Ferreira LAFM, Barruncho LMF (2001) On spanning-tree recombination in evolutionary large-scale network problems-application to electrical distribution planning. IEEE Trans. Evolut. Comput. 5(6):623–630.Crossref, Google Scholar
• Chakrabarty D, Devanur NR, Vazirani VV (2011) New geometry-inspired relaxations and algorithms for the metric Steiner tree problem. Math. Program. 230(1):1–32.Crossref, Google Scholar
• Chou HH, Premkumar G, Chu CH (2001) Genetic algorithms for communications network design—an empirical study of the factors that influence performance. IEEE Trans. Evolut. Comput. 5(3):236–249.Crossref, Google Scholar
• Cordone R, Passeri G (2012) Solving the quadratic minimum spanning tree problem. Appl. Math. Comput. 218(23):11597–11612.Crossref, Google Scholar
• Costa AM (2006) Models and algorithms for two network design problems. Ph.D. thesis, Université de Montréal.Google Scholar
• Costa AM, Cordeau JF, Laporte G (2006) Steiner tree problems with profits. INFOR 44(2):99–115.Google Scholar
• Costa AM, Cordeau JF, Laporte G (2008) Fast heuristics for the Steiner tree problem with revenues, budget and hop constraints. Eur. J. Oper. Res. 190(1):68–78.Crossref, Google Scholar
• Costa AM, Cordeau JF, Laporte G (2009) Models and branch-and-cut algorithms for the Steiner tree problem with revenues, budget and hop constraints. Networks 53(2):141–159.Crossref, Google Scholar
• Ferreira CS, Ochi LS, Parada V, Uchoa E (2012) A GRASP-based approach to the generalized minimum spanning tree problem. Expert Syst. Appl. 39(3):3526–3536.Crossref, Google Scholar
• Fu ZH, Hao JK (2014) Breakout local search for the Steiner tree problem with revenue, budget and hop constraints. Eur. J. Oper. Res. 232(1):209–220.Crossref, Google Scholar
• Garey MR, Graham RL, Johnson DS (1977) The complexity of computing Steiner minimal trees. SIAM J. Appl. Math. 32(4): 835–859.Crossref, Google Scholar
• Golden B, Raghavan S, Stanojević D (2005) Heuristic search for the generalized minimum spanning tree problem. INFORMS J. Comput. 17(3):290–304.Link, Google Scholar
• Hao JK (2012) Memetic algorithms in discrete optimization. Neri F, Cotta C, Moscato P, eds. Handbook of Memetic Algorithms, Studies in Computational Intelligence, Vol. 379 (Springer-Verlag, Berlin), 73–94.Crossref, Google Scholar
• Karp RM (1972) Reducibility among combinatorial problems. Miller RE, Thatcher JW, Bohlinger JD, eds. Complexity of Computer Computations, The IBM Research Symposia Series 1972 (Plenum Press, New York), 85–103.Crossref, Google Scholar
• Lawler E (1975) Combinatorial Optimization: Networks and Matroids (Rinehart and Winston, New York).Google Scholar
• Layeb SB, Hajri I, Haouari M (2013) Solving the Steiner tree problem with revenues, budget and hop constraints to optimality. Proc. 5th Internat. Conf. Modeling, Simulation Appl. Optim., Hammamet, Tunisia, 1–4.Crossref, Google Scholar
• Lü ZP, Glover F, Hao JK (2010) A hybrid metaheuristic approach to solving the UBQP problem. Eur. J. Oper. Res. 207(3):1254–1262.Crossref, Google Scholar
• Moscato P, Cotta C (2003) A gentle introduction to memetic algorithms. Glover F, Kochenberger G, eds. Handbook of Metaheuristics (Kluwer Academic Publishers, Dordrecht, The Netherlands), 105–144.Crossref, Google Scholar
• Öncan T, Punnen AP (2010) The quadratic minimum spanning tree problem: A lower bounding procedure and an efficient search algorithm. Comput. Oper. Res. 37(10):1762–1773.Crossref, Google Scholar
• Porumbel DC, Hao JK, Kuntz P (2010) An evolutionary approach with diversity guarantee and well-informed grouping recombination for graph coloring. Comput. Oper. Res. 37(10):1822–1832.Crossref, Google Scholar
• Potvin J-Y (2009) State-of-the art review—evolutionary algorithms for vehicle routing. INFORMS J. Comput. 21(4):518–548.Link, Google Scholar
• Ribeiro CC, Uchoa E, Werneck RF (2002) A hybrid GRASP with perturbations for the Steiner problem in graphs. INFORMS J. Comput. 14(3):228–246.Link, Google Scholar
• Rothlauf F (2009) An encoding in metaheuristics for the minimum communication spanning tree problem. INFORMS J. Comput. 21(4):575–584.Link, Google Scholar
• Santos M, Drummond LMA, Uchoa E (2010) A distributed dual ascent algorithm for the hop-constrained Steiner sree problem. Oper. Res. Lett. 38(1):57–62.Crossref, Google Scholar
• Sinnl M (2011) Branch-and-price for the Steiner tree problem with revenues, budget and hop constraints. Master’s thesis, Faculty of Computer Science, Vienna University of Technology, Austria.Google Scholar
• Voβ S (1999) The Steiner tree problem with hop constraints. Ann. Oper. Res. 86:321–345.Crossref, Google Scholar
• Voβ S (2006) Steiner tree problems in telecomunications. Pardalos P, Resende MGC, eds. Handbook of Optimization in Telecommunications (Springer, New York), 459–492.Google Scholar