دانلود مقاله ISI انگلیسی شماره 79693
عنوان فارسی مقاله

روش کاهش مبتنی بر برنامه نویسی پویا برای مشکل کوله پشتی 0-1 چند بعدی

کد مقاله سال انتشار مقاله انگلیسی ترجمه فارسی تعداد کلمات
79693 2008 14 صفحه PDF سفارش دهید محاسبه نشده
خرید مقاله
پس از پرداخت، فوراً می توانید مقاله را دانلود فرمایید.
عنوان انگلیسی
A dynamic programming based reduction procedure for the multidimensional 0–1 knapsack problem
منبع

Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)

Journal : European Journal of Operational Research, Volume 186, Issue 1, 1 April 2008, Pages 63–76

کلمات کلیدی
برنامه نویسی پویا؛ برنامه ریزی عدد صحیح؛ مسئله کوله پشتی چند بعدی؛ کاهش متغیر؛ Heuristics
پیش نمایش مقاله
پیش نمایش مقاله روش کاهش مبتنی بر  برنامه نویسی پویا برای مشکل  کوله پشتی 0-1 چند بعدی

چکیده انگلیسی

This paper presents a preprocessing procedure for the 0–1 multidimensional knapsack problem. First, a non-increasing sequence of upper bounds is generated by solving LP-relaxations. Then, a non-decreasing sequence of lower bounds is built using dynamic programming. The comparison of the two sequences allows either to prove that the best feasible solution obtained is optimal, or to fix a subset of variables to their optimal values. In addition, a heuristic solution is obtained. Computational experiments with a set of large-scale instances show the efficiency of our reduction scheme. Particularly, it is shown that our approach allows to reduce the CPU time of a leading commercial software.

خرید مقاله
پس از پرداخت، فوراً می توانید مقاله را دانلود فرمایید.