کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
475815 699378 2017 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Kernel search: A general heuristic for the multi-dimensional knapsack problem
ترجمه فارسی عنوان
جستجو هسته: اکتشافی به طور کلی برای مسئله کوله پشتی چند بعد
کلمات کلیدی
مسئله کوله پشتی چند بعدی؛ متغیرهای دودویی؛ جستجو هسته است؛ بحی اکتشافی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
چکیده انگلیسی

In this paper we apply the kernel search framework to the solution of the strongly NP-hard multi-dimensional knapsack problem (MKP). Kernel search is a heuristic framework based on the identification of a restricted set of promising items (kernel) and on the exact solution of ILP sub-problems. Initially, the continuous relaxation of the MKP, solved on the complete set of available items, is used to identify the initial kernel. Then, a sequence of ILP sub-problems are solved, where each sub-problem is restricted to the present kernel and to a subset of other items. Each ILP sub-problem may find better solutions with respect to the previous one and identify further items to insert into the kernel. The kernel search was initially proposed to solve a complex portfolio optimization problem. In this paper we show that the method has general key features that make it appropriate to solve other combinatorial problems using binary variables to model the decisions to select or not items. We adapt the kernel search to the solution of MKP and show that the method is very effective and efficient with respect to known problem-specific approaches. Moreover, the best known values of some MKP benchmark problems from the MIPLIB library have been improved.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Operations Research - Volume 37, Issue 11, November 2010, Pages 2017–2026
نویسندگان
, , ,