Back to Search
Start Over
A modified VNS metaheuristic for max-bisection problems
- Source :
-
Journal of Computational & Applied Mathematics . Oct2008, Vol. 220 Issue 1/2, p413-421. 9p. - Publication Year :
- 2008
-
Abstract
- Abstract: 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 . It is hard to directly apply the typical VNS metaheuristic to deal with max-bisection problems. In this paper, we skillfully combine the constraint 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. [Copyright &y& Elsevier]
Details
- Language :
- English
- ISSN :
- 03770427
- Volume :
- 220
- Issue :
- 1/2
- Database :
- Academic Search Index
- Journal :
- Journal of Computational & Applied Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 33528472
- Full Text :
- https://doi.org/10.1016/j.cam.2007.08.018