کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
10347885 699358 2013 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Using the primal-dual interior point algorithm within the branch-price-and-cut method
ترجمه فارسی عنوان
با استفاده از الگوریتم نقطه اولیه دوگانه در روش شعاع قیمت و برش
کلمات کلیدی
شعبه - قیمت و برش، نسل ستون، الگوریتم نقطه اولیه دوگانه، مشکل مسیریابی خودرو
ترجمه چکیده
شعبه قیمت و برش ثابت کرده است که یک روش قدرتمند برای حل مشکلات برنامه نویسی عدد صحیح است. این ترکیب تکنیک های تجزیه با تولید هر دو ستون و نابرابری های معتبر است و به محدوده های قوی برای هدایت جستجو در درخت شاخه و محدود متکی است. در این مقاله، ما ارائه می دهیم که چگونه می توان با استفاده از الگوریتم نقطه اولیه دوگانه، عملکرد یک روش قیمت و برش شاخه را بهبود بخشیم. ما در مورد جزئیات چگونگی مقابله با چالش های استفاده از الگوریتم نقطه داخلی با اجزای اصلی روش شعاع قیمت و برش بحث می کنیم. تلاش برای غلبه بر مشکلات، در تعدادی از ویژگی های سودمند ارائه شده توسط رویکرد جدید، سودمند است. ما نتایج محاسباتی را برای حل نمونه های شناخته شده مسائل مسیریابی خودرو با پنجره های زمان، یک مشکل برنامه ریزی عدد صحیح چالش ارائه می کنیم. نتایج نشان می دهد که رویکرد پیشنهادی بهترین عملکرد کلی را در مقایسه با یک روش مشابه قیمت برش و برش ارائه می دهد که بر اساس الگوریتم ساده است.
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
پیش نمایش مقاله
با استفاده از الگوریتم نقطه اولیه دوگانه در روش شعاع قیمت و برش
چکیده انگلیسی
Branch-price-and-cut has proven to be a powerful method for solving integer programming problems. It combines decomposition techniques with the generation of both columns and valid inequalities and relies on strong bounds to guide the search in the branch-and-bound tree. In this paper, we present how to improve the performance of a branch-price-and-cut method by using the primal-dual interior point algorithm. We discuss in detail how to deal with the challenges of using the interior point algorithm with the core components of the branch-price-and-cut method. The effort to overcome the difficulties pays off in a number of advantageous features offered by the new approach. We present the computational results of solving well-known instances of the vehicle routing problem with time windows, a challenging integer programming problem. The results indicate that the proposed approach delivers the best overall performance when compared with a similar branch-price-and-cut method which is based on the simplex algorithm.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Operations Research - Volume 40, Issue 8, August 2013, Pages 2026-2036
نویسندگان
, ,