کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6895640 1445979 2016 14 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
An exact decomposition algorithm for the generalized knapsack sharing problem
ترجمه فارسی عنوان
یک الگوریتم تجزیه دقیق برای مسئله به اشتراک گذاری قیچی عمومی
کلمات کلیدی
تجزیه دقیق، کوله پشتی، اشتراکگذاری، کاهش، کران بالا،
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
چکیده انگلیسی
This paper presents an exact algorithm for solving the knapsack sharing problem with common items. In literature, this problem is also denominated the Generalized Knapsack Sharing Problem (GKSP). The GKSP is NP-hard because it lays on the 0-1 knapsack problem and the knapsack sharing problem. The proposed exact method is based on a rigorous decomposition technique which leads to an intense simplification of the solution procedure for the GKSP. Furthermore, in order to accelerate the procedure for finding the optimum solution, an upper bound and several reduction strategies are considered. Computational results on two sets of benchmark instances from literature show that the proposed method outperforms the other approaches in most instances.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 252, Issue 3, 1 August 2016, Pages 761-774
نویسندگان
, , ,