A modified VNS metaheuristic for max-bisection problems
A modified VNS metaheuristic for max-bisection problems
复制标题
针对最大二分问题的改进的 VNS 元启发式
DOI：
10.1016/j.cam.2007.08.018
复制
发表时间：
2008-10
影响因子：
2.4
通讯作者：
Ling, Ai-fan
中科院分区：
文献类型：
--
作者：
Tang, Le;Xu, Cheng-xian;Ling, Ai-fan
Festa等人提出的可变邻域搜索（VNS）元启发式算法[MAX-CUT问题的随机启发式算法，Optim。]方法软件17(2002)1033-1058]可获得最大切割问题的高质量解。因此，将VNS元启发式算法推广到求解最大等分问题是有价值的。遗憾的是，与最大切问题相比，最大等分问题通过线性约束eTx=0具有更复杂的可行域。很难直接应用典型的VNS元启发式算法来处理最大等分问题。本文将约束条件eTx=0与目标函数巧妙地结合起来，得到了一个等价于最大等分问题的新的优化问题，并对得到的问题采用了一种独特的贪婪局部搜索技术。提出了一种基于贪心局部搜索技术的改进VNS元启发式算法，用于求解最大等分问题。数值结果表明，所提出的方法是有效的，可以得到最大等分问题的高等价解。
Variable neighborhood search (VNS) metaheuristic as presented in Festa et al. [Randomized heuristics for the MAX-CUT problem, Optim. Methods Software 17 (2002) 1033–1058] can obtain high quality solution for max-cut problems. Therefore, it is worthwhile that VNS metaheuristic is extended to solve max-bisection problems. Unfortunately, comparing with max-cut problems, max-bisection problems have more complicated feasible region via the linear constraint eTx=0. It is hard to directly apply the typical VNS metaheuristic to deal with max-bisection problems. In this paper, we skillfully combine the constraint eTx=0 with the objective function, obtain a new optimization problem which is equivalent to the max-bisection problem, and then adopt a distinct greedy local search technique to the resulted problem. A modified VNS metaheuristic based on the greedy local search technique is applied to solve max-bisection problems. Numerical results indicate that the proposed method is efficient and can obtain high equality solution for max-bisection problems.
登录
查看更多内容
影响因子：
1.1
作者：
Frieze, A;Jerrum, M
通讯作者：
Jerrum, M
影响因子：
1
作者：
E. Halperin;Uri Zwick
通讯作者：
E. Halperin;Uri Zwick
DOI：
10.1007/978-1-4615-1507-4
发表时间：
2002
期刊：
--
影响因子：
--
作者：
C. Ribeiro;P. Hansen
通讯作者：
C. Ribeiro;P. Hansen
DOI：
--
发表时间：
2005
期刊：
--
影响因子：
--
作者：
Feng-min;Xu;Cheng-xian;Hong-gang;Xue
通讯作者：
Feng-min;Xu;Cheng-xian;Hong-gang;Xue
DOI：
--
发表时间：
1997-06
期刊：
--
影响因子：
--
作者：
F. Alizadeh;J. Haeberly;M. V. Nayakkankuppa;M. Overton;S. Schmieta
通讯作者：
F. Alizadeh;J. Haeberly;M. V. Nayakkankuppa;M. Overton;S. Schmieta