کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4641944 1632054 2008 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A modified VNS metaheuristic for max-bisection problems
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات کاربردی
پیش نمایش صفحه اول مقاله
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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computational and Applied Mathematics - Volume 220, Issues 1–2, 15 October 2008, Pages 413–421
نویسندگان
, , ,