A modified VNS metaheuristic for max-bisection problems

Variable neighborhood search (VNS) metaheuristic as presented in Festa et al. [Randomized heuristics for the MAX-CUT problem, Optim. Methods Software 17 (2002) 1033–1058] can obtain high quality solution for max-cut problems. Therefore, it is worthwhile that VNS metaheuristic is extended to solve max-bisection problems. Unfortunately, comparing with max-cut problems, max-bisection problems have more complicated feasible region via the linear constraint eTx=0eTx=0. It is hard to directly apply the typical VNS metaheuristic to deal with max-bisection problems. In this paper, we skillfully combine the constraint eTx=0eTx=0 with the objective function, obtain a new optimization problem which is equivalent to the max-bisection problem, and then adopt a distinct greedy local search technique to the resulted problem. A modified VNS metaheuristic based on the greedy local search technique is applied to solve max-bisection problems. Numerical results indicate that the proposed method is efficient and can obtain high equality solution for max-bisection problems.