A note on heuristic approach based on UBQP formulation of the maximum diversity problem
A note on heuristic approach based on UBQP formulation of the maximum diversity problem
复制标题
DOI：
10.1057/s41274-016-0031-4
复制
发表时间：
2017-01
影响因子：
3.6
通讯作者：
B. Alidaee;Haibo Wang
中科院分区：
文献类型：
--
作者：
B. Alidaee;Haibo Wang
最大分集问题(MDP)是一个具有广泛实际应用的具有挑战性的NP-Hard问题。一些研究人员指出了MDP与无约束二次规划(UBQP)之间的密切关系。在本文中，我们从UBQP问题的提法出发，提供了求解MDP思想的程序。我们首先给出了MDP上改进算法的一些局部最优性结果。在此基础上，提出了一套基于序贯改进步骤的高效多元化方法。在一个简单的禁忌搜索中使用了四个版本的方法，并将其应用于互联网上可用的140个基准MDP问题。这些程序立即解决了所有80个中小型问题，成为最著名的解决方案。对于60个大问题中的22个，程序在相当短的CPU时间内显著改进了最知名的解决方案。
The maximum diversity problem (MDP) is a challenging NP-hard problem with a wide range of real applications. Several researchers have pointed out close relationship between the MDP and unconstrained binary quadratic program (UBQP). In this paper, we provide procedures to solve MDP ideas from the UBQP formulation of the problem. We first give some local optimality results forr-flipimprovement procedures on MDP. Then, a set of highly effective diversification approaches based on sequential improvement steps for MDP are presented. Four versions of the approaches are used within a simple tabu search and applied to 140 benchmark MDP problems available on the Internet. The procedures solve all 80 small- to medium-sized problems instantly to the best known solutions. For 22 of the 60 large problems, the procedures improved by significant amounts the best known solutions in reasonably short CPU time.