Solving the Bi-criteria Max-Cut Problem with Different Neighborhood Combination Strategies

Local search is known to be a highly effective metaheuristic framework for solving a number of classical combinatorial optimization problems, which strongly depends on the characteristics of neighborhood structure. In this paper, we integrate different neighborhood combination strategies into the hypervolume-based multi-objective local search algorithm, in order to deal with the bi-criteria max-cut problem. The experimental results indicate that certain combinations are superior to others and the performance analysis sheds lights on the ways to further improvements.