کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
1134643 956074 2011 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Development of core to solve the multidimensional multiple-choice knapsack problem
موضوعات مرتبط
مهندسی و علوم پایه سایر رشته های مهندسی مهندسی صنعتی و تولید
پیش نمایش صفحه اول مقاله
Development of core to solve the multidimensional multiple-choice knapsack problem
چکیده انگلیسی

The multidimensional multiple-choice knapsack problem (MMKP) is an extension of the 0–1 knapsack problem. The core concept has been used to design efficient algorithms for the knapsack problem but the core has not been developed for the MMKP so far. In this paper, we develop an approximate core for the MMKP and utilize it to solve the problem exactly.Computational results show that the algorithm can solve large uncorrelated instances (up to 100 classes and 100 items in each class) and correlated instances with small number of constraints (up to 5) efficiently. In particular, it solves recently published hard instances for the MMKP in less than a second. The algorithm consumes negligible memory, and compared with the best previous exact algorithm for the MMKP performs significantly faster.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Industrial Engineering - Volume 60, Issue 2, March 2011, Pages 349–360
نویسندگان
, ,