A deterministic annealing algorithm for approximating a solution of the max-bisection problem

The max-bisection problem is an NP-hard combinatorial optimization problem. In this paper an equivalent linearly constrained continuous optimization problem is formulated and a deterministic annealing algorithm is proposed for approximating its solution. The algorithm is derived from the introduction of a square-root barrier function, where the barrier parameter behaves as temperature in an annealing procedure and decreases from a sufficiently large positive number to 0. The algorithm searches for a better solution in a feasible descent direction, which has a desired property that lower and upper bounds on variables are always satisfied automatically if the step length is a number between 0 and 1. We prove that the algorithm converges to at least an integral local minimum point of the continuous problem if a local minimum point of the barrier problem is generated for a sequence of descending values of the barrier parameter with zero limit. Numerical results show that the algorithm is much faster than one of the best existing approximation algorithms while they produce more or less the same quality solution. © 2002 Published by Elsevier Science Ltd.