A modified VNS metaheuristic for max-bisection problems

✍ Scribed by Ai-fan Ling; Cheng-xian Xu; Le Tang

• Publisher: Elsevier Science
• Year: 2008
• Tongue: English
• Weight: 163 KB
• Volume: 220
• Category: Article
• ISSN: 0377-0427
• DOI: 10.1016/j.cam.2007.08.018

✦ Synopsis

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 e T x = 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 e T x = 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.