کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
475931 699396 2009 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Fast, effective heuristics for the 0–1 multi-dimensional knapsack problem
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
Fast, effective heuristics for the 0–1 multi-dimensional knapsack problem
چکیده انگلیسی

The objective of the multi-dimensional knapsack problem (MKP) is to find a subset of items with maximum value that satisfies a number of knapsack constraints. Solution methods for MKP, both heuristic and exact, have been researched for several decades. This paper introduces several fast and effective heuristics for MKP that are based on solving the LP relaxation of the problem. Improving procedures are proposed to strengthen the results of these heuristics. Additionally, the heuristics are run with appropriate deterministic or randomly generated constraints imposed on the linear relaxation that allow generating a number of good solutions. All algorithms are tested experimentally on a widely used set of benchmark problem instances to show that they compare favourably with the best-performing heuristics available in the literature.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Operations Research - Volume 36, Issue 5, May 2009, Pages 1602–1607
نویسندگان
, ,