Boosting local search with Lagrangian relaxation

详细信息    查看全文

• 作者：Zhilei Ren (1)
  He Jiang (1)
  Shuwei Zhang (1)
  Jingxuan Zhang (1)
  Zhongxuan Luo (1)
  
• 关键词：Local search ; p ; median ; Lagrangian relaxation ; Lin ; Kernighan neighborhood
• 刊名：Journal of Heuristics
• 出版年：2014
• 出版时间：October 2014
• 年：2014
• 卷：20
• 期：5
• 页码：589-615
• 全文大小：575 KB
• 参考文献：1. Aiex, R.M., Resende, M.G., Ribeiro, C.C.: TTT plots: a perl program to create time-to-target plots. Optim. Lett. 1(4), 355鈥?66 (2007) CrossRef
  2. Alekseeva, E., Kochetov, Y., Plyasunov, A.: Complexity of local search for the p-median problem. Eur. J. Oper. Res. 191(3), 736鈥?52 (2008) CrossRef
  3. Avella, P., Sassano, A., Vasil鈥檈v, I.: Computational study of large-scale p-median problems. Math. Program. 109(1), 89鈥?14 (2007) CrossRef
  4. Beasley, J.E.: Lagrangean heuristics for location problems. Eur. J. Oper. Res. 65(3), 383鈥?99 (1993) CrossRef
  5. Belov, A., J盲rvisalo, M., Stachniak, Z.: Depth-driven circuit-level stochastic local search for sat. In: Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, vol. 1, pp. 504鈥?09. AAAI Press, Menlo Park (2011)
  6. Bennell, J., Song, X.: A beam search implementation for the irregular shape packing problem. J. Heuristics 16(2), 167鈥?88 (2010) CrossRef
  7. Brimberg, J., Mladenovi膰, N., Uro拧evi膰, D.: Local and variable neighborhood search for the k-cardinality subgraph problem. J. Heuristics 14(5), 501鈥?17 (2008) CrossRef
  8. Brueggemann, T., Hurink, J.L.: Matching based very large-scale neighborhoods for parallel machine scheduling. J. Heuristics 17(6), 637鈥?58 (2011) CrossRef
  9. Ceschia, S., Schaerf, A.: Local search for a multi-drop multi-container loading problem. J. Heuristics 19(2), 275鈥?94 (2013) CrossRef
  10. Christofides, N., Beasley, J.E.: A tree search algorithm for the p-median problem. Eur. J. Oper. Res. 10(2), 196鈥?04 (1982) CrossRef
  11. Climer, S., Zhang, W.: Searching for backbones and fat: a limit-crossing approach with applications. In: Proceedings of The National Conference on Artificial Intelligence, pp 707鈥?12. AAAI Press, Menlo Park (2002)
  12. Croce, F., Ghirardi, M., Tadei, R.: Recovering beam search: enhancing the beam search approach for combinatorial optimization problems. J. Heuristics 10(1), 89鈥?04 (2004) CrossRef
  13. Fischetti, M., Lodi, A.: Local branching. Math. Program. 98(1鈥?), 23鈥?7 (2003) CrossRef
  14. Garc铆a, S., Labb茅, M., Mar铆n, A.: Solving large p-median problems with a radius formulation. INFORMS J. Comput. 23(4), 546鈥?56 (2011) CrossRef
  15. Glover, F.: Tabu search-part I. ORSA J. Comput. 1(3), 190鈥?06 (1989) CrossRef
  16. Glover, F.: Tabu search-part II. ORSA J. Comput. 2(1), 4鈥?2 (1990) CrossRef
  17. Gutin, G., Karapetyan, D.: Local search heuristics for the multidimensional assignment problem. Graph Theory, Computational Intelligence and Thought, pp. 100鈥?15. Springer, Berlin (2009) CrossRef
  18. Hakimi, S.L.: Optimum locations of switching centers and the absolute centers and medians of a graph. Oper. Res. 12(3), 450鈥?59 (1964) CrossRef
  19. Hansen, P., Mladenovic, N.: Variable neighborhood search for the p-median. Locat. Sci. 5(4), 207鈥?26 (1997) CrossRef
  20. Helsgaun, K.: General k-opt submoves for the Lin鈥揔ernighan TSP heuristic. Math. Program. Comput. 1(2鈥?), 119鈥?63 (2009) CrossRef
  21. Hoos, H.H., St眉tzle, T.: Stochastic Local Search. Foundations and Applications. Elsevier, Amsterdam (2005)
  22. J盲rvinen, P., Rajala, J., Sinervo, H.: A branch-and-bound algorithm for seeking the p-median. Oper. Res. 20(1), 173鈥?78 (1972) CrossRef
  23. Kernighan, B., Lin, S.: An eflicient heuristic procedure for partitioning graphs. Bell Syst. Tech. J. 29, 209 (1970)
  24. Kochetov, Y., Levanova, T., Alekseeva, E., Loresh, M.: Large neighborhood local search for the p-median problem. Yugosl. J. Oper. Res. 15(1), 53鈥?3 (2005) CrossRef
  25. Li, C.M., Quan, Z.: An efficient branch-and-bound algorithm based on MaxSAT for the maximum clique problem. In: Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence, pp. 128鈥?33 (2010)
  26. Mladenovic, N., Brimberg, J., Hansen, P., Moreno-Prez, J.A.: The p-median problem: a survey of metaheuristic approaches. Eur. J. Oper. Res. 179(3), 927鈥?39 (2007) CrossRef
  27. Puchinger, J., Raidl, G.R.: Bringing order into the neighborhoods: relaxation guided variable neighborhood search. J. Heuristics 14(5), 457鈥?72 (2008) CrossRef
  28. Pullan, W.: A population based hybrid metaheuristic for the p-median problem. In: 2008 IEEE Congress on Evolutionary Computation, pp. 75鈥?2 (2008)
  29. Reese, J.: Solution methods for the p-median problem: an annotated bibliography. Networks 48(3), 125鈥?42 (2006) CrossRef
  30. Reinelt, G.: TSPLIB-a traveling salesman problem library. ORSA J. Comput. 3, 376鈥?84 (1991) CrossRef
  31. Ren, Z., Jiang, H., Xuan, J., Hu, Y., Luo, Z.: New insights into diversification of hyper-heuristics. IEEE Trans. Cybern (in press) (2013)
  32. Ren, Z., Jiang, H., Xuan, J., Luo, Z.: An accelerated-limit-crossing-based multilevel algorithm for the p-median problem. IEEE Trans. Syst. Man Cybern. B 42(4), 1187鈥?202 (2012a) CrossRef
  33. Ren, Z., Jiang, H., Xuan, J., Luo, Z.: Hyper-heuristics with low level parameter adaptation. Evol. Comput. 20(2), 189鈥?27 (2012b) CrossRef
  34. Resende, M.G., Werneck, R.F.: On the implementation of a swap-based local search procedure for the p-median problem. In: Proceedings of the Fifth Workshop on Algorithm Engineering and Experiments, pp. 119鈥?27 (2003)
  35. Resende, M.G.C., Werneck, R.F.: A hybrid heuristic for the p-median problem. J. Heuristics 10(1), 59鈥?8 (2004) CrossRef
  36. Riise, A., Burke, E.K.: Local search for the surgery admission planning problem. J. Heuristics 17(4), 389鈥?14 (2011) CrossRef
  37. Rosing, K.E., Revelle, C.S., Schilling, D.A.: A gamma heuristic for the p-median problem. Eur. J. Oper. Res. 117(3), 522鈥?32 (1999) CrossRef
  38. Senne, E., Lorena, L.: Lagrangean/surrogate heuristics for p-median problems. Computing Tools for Modeling, Optimization and Simulation: Interfaces in Computer Science and Operations Research. Kluwer Academic, Dordrecht (2000)
  39. Smith-Miles, K.A.: Cross-disciplinary perspectives on meta-learning for algorithm selection. ACM Comput. Surv. 41(1), 6:1鈥?:25 (2009)
  40. Teitz, M.B., Bart, P.: Heuristic methods for estimating the generalized vertex median of a weighted graph. Oper. Res. 16(5), 955鈥?61 (1968) CrossRef
  41. Vela, C.R., Varela, R., Gonz谩lez, M.A.: Local search and genetic algorithm for the job shop scheduling problem with sequence dependent setup times. J. Heuristics 16(2), 139鈥?65 (2010) CrossRef
  42. Whitaker, R.: A fast algorithm for the greedy interchange for large-scale clustering and median location problems. INFOR J. 21(2), 95鈥?08 (1983)
  
• 作者单位：Zhilei Ren (1)
  He Jiang (1)
  Shuwei Zhang (1)
  Jingxuan Zhang (1)
  Zhongxuan Luo (1)
  
  1. School of Software, Dalian University of Technology, Dalian, China
  
• ISSN：1572-9397

文摘

Local search algorithms play an essential role in solving large-scale combinatorial optimization problems. Traditionally, the local search procedure is guided mainly by the objective function of the problem. Hence, the greedy improvement paradigm poses the potential threat of prematurely getting trapped in low quality attraction basins. In this study, we intend to utilize the information extracted from the relaxed problem, to enhance the performance of the local search process. Considering the Lin-Kernighan-based local search (LK-search) for the p-median problem as a case study, we propose the Lagrangian relaxation Assisted Neighborhood Search (LANS). In the proposed algorithm, two new mechanisms, namely the neighborhood reduction and the redundancy detection, are developed. The two mechanisms exploit the information gathered from the relaxed problem, to avoid the search from prematurely targeting low quality directions, and to cut off the non-promising searching procedure, respectively. Extensive numerical results over the benchmark instances demonstrate that LANS performs favorably to LK-search, which is among the state-of-the-art local search algorithms for the p-median problem. Furthermore, by embedding LANS into other heuristics, the best known upper bounds over several benchmark instances could be updated. Besides, run-time distribution analysis is also employed to investigate the reason why LANS works. The findings of this study confirm that the idea of improving local search by leveraging the information induced from relaxed problem is feasible and practical, and might be generalized to a broad class of combinatorial optimization problems.