Dang Chuangyin, Ma Wei, Liang Jiye
Department of Manufacturing Engineering and Engineering Management, City University of Hong Kong, Kowloon, Hong Kong.
Neural Netw. 2009 Jan;22(1):58-66. doi: 10.1016/j.neunet.2008.09.008. Epub 2008 Sep 30.
The min-bisection problem is an NP-hard combinatorial optimization problem. In this paper an equivalent linearly constrained continuous optimization problem is formulated and an algorithm is proposed for approximating its solution. The algorithm is derived from the introduction of a logarithmic-cosine barrier function, where the barrier parameter behaves as temperature in an annealing procedure and decreases from a sufficiently large positive number to zero. The algorithm searches for a better solution in a feasible descent direction, which has a desired property that lower and upper bounds are always satisfied automatically if the step length is a number between zero and one. We prove that the algorithm converges to at least a local minimum point of the problem if a local minimum point of the barrier problem is generated for a sequence of descending values of the barrier parameter with a limit of zero. Numerical results show that the algorithm is much more efficient than two of the best existing heuristic methods for the min-bisection problem, Kernighan-Lin method with multiple starting points (MSKL) and multilevel graph partitioning scheme (MLGP).
最小二等分问题是一个NP难的组合优化问题。本文提出了一个与之等价的线性约束连续优化问题，并给出了一种逼近其解的算法。该算法是通过引入对数余弦障碍函数推导出来的，其中障碍参数在退火过程中起到温度的作用，并从一个足够大的正数减小到零。该算法在可行下降方向上搜索更好的解，该方向具有一个期望的性质，即如果步长在零和一之间，则总是自动满足上下界。我们证明，如果对于障碍参数的一系列递减值生成障碍问题的局部最小点且极限为零，则该算法收敛到该问题的至少一个局部最小点。数值结果表明，该算法比最小二等分问题的两种现有最佳启发式方法——多起点Kernighan-Lin方法（MSKL）和多层图划分方案（MLGP）效率更高。
