کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4958870 | 1445458 | 2018 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Exact approaches for the knapsack problem with setups
ترجمه فارسی عنوان
رویکرد دقیق برای مشکل حلقه با تنظیمات
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
مشکلات کوله پشتی، نسل ستون، آرامش الگوریتم های شعبه و محدود، آزمایش های محاسباتی،
ترجمه چکیده
ما یک تعریف از مشکل حلقه ای را در نظر می گیریم که در آن اقلام به کلاس تقسیم می شوند، هر کدام با هزینه ثابت و ظرفیت مشخص می شوند. ما سه فرمول بندی برنامه نویسی صحیح خطی جایگزین را مطالعه می کنیم. برای هر فرمول بندی، ما یک الگوریتم کارآمد برای محاسبه آرام سازی برنامه ریزی خطی (یکی از آنها بر اساس تکنیک های ستون ستون) طراحی شده است. ما از لحاظ نظری توانایی آرامش را مقایسه می کنیم و نتایج خاصی را برای یک پرونده مربوطه که در موارد معین از ادبیات مطرح است، می گیریم. در نهایت، ما الگوریتم های فوق را به یک طرح شمارش ضرایب یکپارچه جاسازی می کنیم که به صورت موازی با یک الگوریتم پیشرفته پویا برنامه ریزی شده به طور موثر برای بهینه سازی مشکل حل می شود. یک تجزیه و تحلیل محاسباتی وسیع نشان می دهد که الگوریتم دقیق جدید ما قادر است به طور موثر حل تمام موارد ادبیات را ارائه دهد و بهترین نمونه برای تعداد نمونه هایی از کلاس ها باشد.
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
چکیده انگلیسی
We consider a generalization of the knapsack problem in which items are partitioned into classes, each characterized by a fixed cost and capacity. We study three alternative Integer Linear Programming formulations. For each formulation, we design an efficient algorithm to compute the linear programming relaxation (one of which is based on Column Generation techniques). We theoretically compare the strength of the relaxations and derive specific results for a relevant case arising in benchmark instances from the literature. Finally, we embed the algorithms above into a unified implicit enumeration scheme which is run in parallel with an improved Dynamic Programming algorithm to effectively solve the problem to proven optimality. An extensive computational analysis shows that our new exact algorithm is capable of efficiently solving all the instances of the literature and turns out to be the best algorithm for instances with a low number of classes.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Operations Research - Volume 90, February 2018, Pages 208-220
Journal: Computers & Operations Research - Volume 90, February 2018, Pages 208-220
نویسندگان
Fabio Furini, Michele Monaci, Emiliano Traversi,