Boosting local search with Lagrangian relaxation
Boosting local search with Lagrangian relaxation
复制标题
DOI：
10.1007/s10732-014-9255-0
复制
发表时间：
2014-10
影响因子：
2.7
通讯作者：
Zhilei Ren;He Jiang;Shuwei Zhang;Jingxuan Zhang;Zhongxuan Luo
中科院分区：
文献类型：
--
作者：
Zhilei Ren;He Jiang;Shuwei Zhang;Jingxuan Zhang;Zhongxuan Luo
局部搜索算法在求解大规模组合优化问题中起着重要的作用。传统上，局部搜索过程主要由问题的目标函数来指导。因此，贪婪的改进范式构成了过早陷入低质量吸引力盆地的潜在威胁。在这项研究中，我们打算利用从放松问题中提取的信息，以提高局部搜索过程的性能。考虑到基于Lin-Kernighan的局部搜索（LK-搜索）的p-中位数问题作为一个案例研究，我们提出了拉格朗日松弛辅助邻域搜索（局域网）。在该算法中，两个新的机制，即邻域减少和冗余检测，开发。这两种机制利用从放松的问题中收集的信息，以避免过早地针对低质量的方向进行搜索，并切断非有前途的搜索过程，分别。大量的数值实验结果表明，局域网的性能优于LK-搜索，这是最先进的局部搜索算法的p-中位数问题。此外，通过将局域网嵌入到其他算法中，可以更新多个基准实例上的最佳已知上界。此外，运行时分布分析也被用来调查为什么局域网的工作。研究结果证实了利用松弛问题的信息来改进局部搜索的思想是可行的和实用的，并且可以推广到更广泛的组合优化问题。
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.