کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
475289 699275 2010 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Hard multidimensional multiple choice knapsack problems, an empirical study
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
Hard multidimensional multiple choice knapsack problems, an empirical study
چکیده انگلیسی

Recent advances in algorithms for the multidimensional multiple choice knapsack problems have enabled us to solve rather large problem instances. However, these algorithms are evaluated with very limited benchmark instances. In this study, we propose new methods to systematically generate comprehensive benchmark instances. Some instances with special correlation properties between parameters are found to be several orders of magnitude harder than those currently used for benchmarking the algorithms. Experiments on an existing exact algorithm and two generic solvers show that instances whose weights are uncorrelated with the profits are easier compared with weakly or strongly correlated cases. Instances with classes containing similar set of profits for items and with weights strongly correlated to the profits are the hardest among all instance groups investigated. These hard instances deserve further study and understanding their properties may shed light to better algorithms.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Operations Research - Volume 37, Issue 1, January 2010, Pages 172–181
نویسندگان
, , ,