Mathematical Problems in Engineering
Volume 2012 (2012), Article ID 475018, 16 pages
http://dx.doi.org/10.1155/2012/475018
Research Article

A VNS Metaheuristic with Stochastic Steps for Max 3-Cut and Max 3-Section

Ai-fan Ling1,2

1Research Center of Security and Future, School of Finance, Jiangxi University of Finance and Economics, Nanchang 330013, China
2Key Laboratory of Management, Decision and Information Systems, Academy of Mathematics and Systems Science, CAS, Beijing 100190, China

Received 15 February 2012; Accepted 30 May 2012

Academic Editor: John Gunnar Carlsson

Copyright © 2012 Ai-fan Ling. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Abstract

A heuristic algorithm based on VNS is proposed to solve the Max 3-cut and Max 3-section problems. By establishing a neighborhood structure of the Max 3-cut problem, we propose a local search algorithm and a variable neighborhood global search algorithm with two stochastic search steps to obtain the global solution. We give some numerical results and comparisons with the well-known 0.836-approximate algorithm. Numerical results show that the proposed heuristic algorithm can obtain efficiently the high-quality solutions and has the better numerical performance than the 0.836-approximate algorithm for the NP-Hard Max 3-cut and Max 3-section problems.