کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6895413 1445974 2016 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Robust efficiency measures for linear knapsack problem variants
ترجمه فارسی عنوان
معیارهای بازدهی قوی برای انواع خط مشی خطی
کلمات کلیدی
بهینه سازی ترکیبی، ابتکاری، الگوریتم ژنتیک، مشکل حلقه
ترجمه چکیده
برنامه های کاربردی بهینه سازی ترکیبی متعددی، از قبیل مشکل ترکیبی محصول خرده فروشان تلفن همراه، استفاده از چندین و چند بعدی انواع حلقه کوله پشتی است که در آن محدودیت های پیچیده ای وجود دارد که نیاز به جمع بندی وزنی متغیرها دارند که کمتر یا برابر با مقدار غیرقابل انحراف و محدودیت تقاضای چندگانه نیاز به جمع بندی وزنی متغیرهایی که بیشتر یا برابر یک مقدار غیرقابل برگشت هستند. هدف از این مقاله نشان دادن این است که متغیرهای هسته ای و اقدامات کارآیی، مفاهیمی که در حل مسائل روزمره مشکلاتی برای حلقه های دوتایی و برخی از انواع آن استفاده می شود، می توانند به نوع چندبعدی و چندبعدی مسئله حلقه بسته شوند. به طور خاص، محاسبات اندازه گیری کارایی جدید ارائه شده است و خواص آنها به صورت ریاضی اثبات شده و تجربی نشان داده شده است. سهم این اقدامات در مورد تحقیق در مورد مسئله پیچاندن چرمی این است که این اقدامات برای همه انواع مشکلات حلقه ای با یک تابع هدف تک خط و محدودیت های خطی هر مقدار قابل اجرا است. کاربرد این اقدامات جدید با توسعه سه روش اکتشافی نشان داده شده است: یک اکتشاف ثابت هسته ای، یک الگوریتم ژنتیک و جستجوی اکتشافی هسته ای. نتایج این آزمایش ها با نتایج یک حل کننده تجاری و یک اکتشافی موجود مقایسه شده است. یافته های این آزمایش ها نشان می دهد که اکتشافات جستجوی ثابت هسته ای و هسته برای این مقاله برای حل مشکل سخت افزاری چند بعدی و چندبعدی مشکل تر است.
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
پیش نمایش مقاله
معیارهای بازدهی قوی برای انواع خط مشی خطی
چکیده انگلیسی
Numerous combinatorial optimization applications, such as the mobile retailer product mix problem, utilize the multidemand, multidimensional knapsack problem variant in which there are multiple knapsack constraints requiring a weighted summation of the variables to be less than or equal to a nonnegative value and multiple demand constraints requiring a weighted summation of the variables to be greater than or equal to a nonnegative value. The purpose of this paper is to demonstrate that core variables and efficiency measures, concepts used in the most efficient solvers to-date for binary knapsack problems and some of its variants, can be extended to the multidemand, multidimensional knapsack problem variant. Specifically, new efficiency measure calculations are provided and their properties are mathematically proven and experimentally demonstrated. The contribution of such measures to knapsack problem research is that these measures are applicable to all knapsack problem variants with a single linear objective function and linear constraints of any quantity. The applicability of these new measures is demonstrated through the development of three heuristic procedures: a Fixed-Core heuristic, a Genetic Algorithm, and a Kernel Search heuristic. The results from these tests are compared with the results from a commercial solver and an existing heuristic. The findings from these tests demonstrate that the Fixed-Core and Kernel Search heuristics developed for this paper are the most efficient solvers to-date for hard multidemand, multidimensional knapsack problems.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 254, Issue 2, 16 October 2016, Pages 398-409
نویسندگان
, ,