Advanced Scatter Search for the Max-Cut Problem
Advanced Scatter Search for the Max-Cut Problem
复制标题
DOI：
10.1287/ijoc.1080.0275
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
R. Martí;A. Duarte;M. Laguna
中科院分区：
文献类型：
--
作者：
R. Martí;A. Duarte;M. Laguna
最大割问题是将一个加权图的节点划分成两个子集，使得连接这两个子集的弧上权重之和最大化。这是一个NP-Hard问题，也可以表示为整数二次规划。自20世纪70年代以来，已经发展了几种求解方法，并应用于各种领域，特别是在工程和布局设计中。我们提出了一种基于分散搜索方法的启发式方法来寻找该优化问题的近似解。我们的求解过程结合了分散搜索框架中的一些创新特征：(1)解决最大多样性问题以增加参考集的多样性，(2)动态调整搜索中的关键参数，以及(3)自适应地选择组合方法。我们进行了大量的计算实验，首先研究关键散布搜索元素的变化的影响，然后比较我们的建议与以前的求解过程的效率。
The max-cut problem consists of finding a partition of the nodes of a weighted graph into two subsets such that the sum of the weights on the arcs connecting the two subsets is maximized. This is an NP-hard problem that can also be formulated as an integer quadratic program. Several solution methods have been developed since the 1970s and applied to a variety of fields, particularly in engineering and layout design. We propose a heuristic method based on the scatter-search methodology for finding approximate solutions to this optimization problem. Our solution procedure incorporates some innovative features within the scatter-search framework: (1) the solution of the maximum diversity problem to increase diversity in the reference set, (2) a dynamic adjustment of a key parameter within the search, and (3) the adaptive selection of a combination method. We perform extensive computational experiments to first study the effect of changes in critical scatter-search elements and then to compare the efficiency of our proposal with previous solution procedures.