Path relinking for unconstrained binary quadratic programming
Path relinking for unconstrained binary quadratic programming
复制标题
DOI：
10.1016/j.ejor.2012.07.012
复制
发表时间：
2012-12
期刊：
影响因子：
--
通讯作者：
Yang Wang;Zhipeng Lü;F. Glover;Jin-Kao Hao
中科院分区：
文献类型：
--
作者：
Yang Wang;Zhipeng Lü;F. Glover;Jin-Kao Hao
本文提出了两种求解无约束二元二次规划（UBQP）问题的路径重连算法。一种是基于贪婪策略生成从初始解到引导解的重连路径，另一种是随机操作。我们展示了五组基准测试的广泛计算结果，包括31个大型随机UBQP实例和103个来自MaxCut问题的结构化实例。与几个国家的最先进的算法的比较表明，我们提出的算法在解决方案的质量和计算效率方面的有效性。值得注意的是，这两种算法都能够改善103个MaxCut实例中近40%的先前最佳已知结果。
This paper presents two path relinking algorithms to solve the unconstrained binary quadratic programming (UBQP) problem. One is based on a greedy strategy to generate the relinking path from the initial solution to the guiding solution and the other operates in a random way. We show extensive computational results on five sets of benchmarks, including 31 large random UBQP instances and 103 structured instances derived from the MaxCut problem. Comparisons with several state-of-the-art algorithms demonstrate the efficacy of our proposed algorithms in terms of both solution quality and computational efficiency. It is noteworthy that both algorithms are able to improve the previous best known results for almost 40 percent of the 103 MaxCut instances.