An Accelerated-Limit-Crossing-Based Multilevel Algorithm for the $p$-Median Problem
An Accelerated-Limit-Crossing-Based Multilevel Algorithm for the $p$-Median Problem
复制标题
DOI：
10.1109/tsmcb.2012.2188100
复制
发表时间：
2012-08
期刊：
影响因子：
--
通讯作者：
Zhilei Ren;He Jiang;J. Xuan;Zhongxuan Luo
中科院分区：
文献类型：
--
作者：
Zhilei Ren;He Jiang;J. Xuan;Zhongxuan Luo
在本文中，我们研究如何设计一个有效的启发式算法的指导下的骨干和脂肪，在上下文中的p-中位数问题。给定一个问题实例，骨干变量被定义为所有最优解所共有的变量，而胖变量被定义为每个最优解中不存在的变量。骨干（脂肪）变量的识别是必不可少的启发式算法利用这种结构。由于现有的精确识别方法，即，极限穿越（LC）是一种耗时且对上界敏感的算法，很难将其引入启发式算法设计中。在本文中，我们开发了加速LC（ALC）为基础的多级算法（ALCMA）。与LC重复运行耗时的拉格朗日松弛（LR）过程相反，ALC被引入ALCMA中，使得LR仅执行一次，并且每个骨架（脂肪）变量可以在O（1）时间内确定。同时，通过动态伪上限机制消除了上限敏感性。通过将ALC与伪上界相结合，ALCMA可以在一系列缩减的搜索空间内有效地找到高质量的解。大量的实证结果表明，ALCMA优于现有的启发式算法的平均解质量。
In this paper, we investigate how to design an efficient heuristic algorithm under the guideline of the backbone and the fat, in the context of the p-median problem. Given a problem instance, the backbone variables are defined as the variables shared by all optimal solutions, and the fat variables are defined as the variables that are absent from every optimal solution. Identification of the backbone (fat) variables is essential for the heuristic algorithms exploiting such structures. Since the existing exact identification method, i.e., limit crossing (LC), is time consuming and sensitive to the upper bounds, it is hard to incorporate LC into heuristic algorithm design. In this paper, we develop the accelerated-LC (ALC)-based multilevel algorithm (ALCMA). In contrast to LC which repeatedly runs the time-consuming Lagrangian relaxation (LR) procedure, ALC is introduced in ALCMA such that LR is performed only once, and every backbone (fat) variable can be determined in O(1) time. Meanwhile, the upper bound sensitivity is eliminated by a dynamic pseudo upper bound mechanism. By combining ALC with the pseudo upper bound, ALCMA can efficiently find high-quality solutions within a series of reduced search spaces. Extensive empirical results demonstrate that ALCMA outperforms existing heuristic algorithms in terms of the average solution quality.