A deterministic annealing algorithm for approximating a solution of the min-bisection problem.
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).
Dang
Chuangyin
C
Department of Manufacturing Engineering and Engineering Management, City University of Hong Kong, Kowloon, Hong Kong. mecdang@cityu.edu.hk
Ma
Wei
W
Liang
Jiye
J
D000465:Algorithms; D001185:Artificial Intelligence; D003198:Computer Simulation; D016571:Neural Networks, Computer