APPLICATION OF MULTISTART TABU SEARCH TO THE MAX-CUT PROBLEM

Abstract

In this paper, we investigate two multistart tabu search implementations for the MAX-CUT problem: an algorithm based on application of a steepest ascent heuristic to specially constructed subproblems and the classical random restart method. Computational results on three sets of standard test problems indicate that the first of these techniques outperforms the second one and is very competitive when compared to other heuristic algorithms.