کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6894433 | 1445922 | 2018 | 48 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Accelerating the Branch-and-Price Algorithm Using Machine Learning
ترجمه فارسی عنوان
سرعت بخشیدن به الگوریتم شعب و قیمت با استفاده از یادگیری ماشین
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
چکیده انگلیسی
This study presents a widely applicable approach to accelerate the computation time of the Branch-and-Price (BaP) algorithm, which is a very powerful exact method used for solving complex combinatorial problems. Existing studies indicate that the most computationally demanding element of the BaP algorithm is the pricing problem. The case-studies presented in this paper show that more than 90% of the total Central Processing Unit (CPU) processing time is consumed by solving the pricing problem. The pricing problem is repetitive in nature and it solves the same problem from scratch differing only in the input dual prices. In this study, we demonstrate how to utilize the knowledge gained from previous executions of the pricing problem to reduce the solution space of pricing problems solved in future iterations. The solution is based on an online machine learning method that is not tailor-made for a specific problem (but needs a proper problem-dependent feature selection) and uses a very fast regression model that generates negligible overhead compared to the total CPU processing time of the BaP algorithm. The method predicts a tight upper bound for the current iteration of the pricing problem while preserving the exactness of the BaP algorithm. The efficiency of the proposed approach is demonstrated by two distinct case-studies: the nurse rostering problem and the scheduling of time-division multiplexing for multi-core platforms. The experiments carried out for both case-studies using benchmark instances from the literature show a 40% and 22% average CPU time reduction for the entire BaP algorithm.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 271, Issue 3, 16 December 2018, Pages 1055-1069
Journal: European Journal of Operational Research - Volume 271, Issue 3, 16 December 2018, Pages 1055-1069
نویسندگان
Roman VáclavÃk, AntonÃn Novák, PÅemysl Šůcha, ZdenÄk Hanzálek,