کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6894443 | 1445923 | 2018 | 19 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Stabilized branch-and-price algorithms for vector packing problems
ترجمه فارسی عنوان
الگوریتم های شاخه و قیمت پایدار برای مشکلات بسته بندی بردار
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
برش دادن، بسته بندی برداری مشکل کوتاهترین مسیر با محدودیت منابع، نابرابری بهینه دوام، پایدارسازی،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
چکیده انگلیسی
This paper considers packing and cutting problems in which a packing/cutting pattern is constrained independently in two or more dimensions. Examples are restrictions with respect to weight, length, and value. We present branch-and-price algorithms to solve these vector packing problems (VPPs) exactly. The underlying column-generation procedure uses an extended master program that is stabilized by (deep) dual-optimal inequalities. While some inequalities are added to the master program right from the beginning (static version), other violated dual-optimal inequalities are added dynamically. The column-generation subproblem is a multidimensional knapsack problem, either binary, bounded, or unbounded depending on the specific master problem formulation. Its fast resolution is decisive for the overall performance of the branch-and-price algorithm. In order to provide a generic but still efficient solution approach for the subproblem, we formulate it as a shortest path problem with resource constraints (SPPRC), yielding the following advantages: (i)Â Violated dual-optimal inequalities can be identified as a by-product of the SPPRC labeling approach and thus be added dynamically; (ii)Â branching decisions can be implemented into the subproblem without deteriorating its resolution process; and (iii)Â larger instances of higher-dimensional VPPs can be tackled with branch-and-price for the first time. Extensive computational results show that our branch-and-price algorithms are capable of solving VPP benchmark instances effectively.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 271, Issue 2, 1 December 2018, Pages 401-419
Journal: European Journal of Operational Research - Volume 271, Issue 2, 1 December 2018, Pages 401-419
نویسندگان
Katrin HeÃler, Timo Gschwind, Stefan Irnich,