کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10346188 | 698774 | 2013 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
An effective GRASP and tabu search for the 0-1 quadratic knapsack problem
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
As a generalization of the classical 0-1 knapsack problem, the 0-1 Quadratic Knapsack Problem (QKP) that maximizes a quadratic objective function subject to a linear capacity constraint is NP-hard in strong sense. In this paper, we propose a memory based Greedy Randomized Adaptive Search Procedures (GRASP) and a tabu search algorithm to find near optimal solution for the QKP. Computational experiments on benchmarks and on randomly generated instances demonstrate the effectiveness and the efficiency of the proposed algorithms, which outperforms the current state-of-the-art heuristic Mini-Swarm in computational time and in the probability to achieve optimal solutions. Numerical results on large-sized instances with up to 2000 binary variables have also been reported.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Operations Research - Volume 40, Issue 5, May 2013, Pages 1176-1185
Journal: Computers & Operations Research - Volume 40, Issue 5, May 2013, Pages 1176-1185
نویسندگان
Zhen Yang, Guoqing Wang, Feng Chu,