شاخه و برش

شاخه و برش (Branch and cut) روشی است در بهینه سازی ترکیبیاتی برای حل مسائل برنامه‌های خطی عدد صحیح، این مسائل، برنامه نویسی خطی هستند که در آن‌ها برخی یا همهٔ مجهولات به مقادیر اعداد صحیح محدود‌اند.^[۱] شاخه و برش شامل اجرای یک الگوریتم شاخه و حد، و استفاده از سطح برش به منظور محدود کردن راحتی ^relaxation در برنامه‌نویسی خطی است. لازم به ذکر است که اگر برش‌ها تنها به منظور محدود کردن راحتی اولیه برنامه نویسی خطی مورد استفاده قرار گیرند؛ الگوریتم برش و شاخه نامیده می‌شود.

شرح الگوریتم

این روش برنامه‌های خطی بدون قید اعداد صحیح را با استفاده از الگوریتم غیر مرکب معمولی حل می‌کند. زمانی که یک راه حل بهینه پیدا شد، و این راه حل یک مقدار غیر صحیح برای متغیری که قرار بود مقدارش صحیح باشد داشت؛ برای یافتن قیود خطی بیشتر که توسط تمام نقاط صحیح ممکن ارضا شوند ولی به وسیله جواب کسری حاضر نقض شوند ممکن است از الگوریتم سطح برش استفاده شود. این نامساوی‌ها ممکن است به برنامه خطی اضافه شوند، به طوری که دوباره حل کردن آن به جوابی متفاوت منجر خواهد شد که اگر امیدوار باشیم «کمتر کسری» است.

در این نقطه، بخش شاخه و حد الگوریتم آغاز شده‌است. مسئله به چندین (معمولاً دو) نسخه تقسیم می‌شود. برنامه‌های خطی جدید به وسیلهٔ روش غیر مرکب حل می‌شوند و فرایند تکرار می‌شود. در طول فرایند شاخه و حد، جواب‌های غیر انتگرالی برای، راحتی برنامه نویسی خطی، به عنوان حد بالا به کار گرفته می‌شوند و جواب‌های انتگرالی به عنوان حد پایین. یک گره می‌تواند هرس شود اگر یک حد بالا، پایین‌تر از حد پایین موجود باشد. همچنین در هنگام حل راحتی lp ممکن است سطح برش اضافی تولید گردد، که یا برش‌های سراسری هستند به عنوان مثال معتبر برای تمام جواب‌های صحیح، ویا برش‌های محلی، به آن معنی که آن‌ها به وسیلهٔ تمامی جوابهایی که قیود جانبی زیر درخت شاخه و حد در نظر گرفته شدهٔ کنونی را برآورده می‌کنند، ارضا می‌شوند.

الگوریتم به صورت زیر خلاصه شده‌است. الگوریتم فرض می‌کند ILP (برنامه‌نویسی منطقی استقرایی) یک مسئلهٔ بیشینه سازی است.

افزودن ILP اولیه به L، لیست مسائل فعال
قرار دادن $x*={\text{null}}$ و $v*=-\infty$
تا زمانی که $L$ $L$ خالی نیست
1. انتخاب و حذف یک مسئله از $L$
2. حل Relaxation مسئله
3. اگر جواب مسئله غیر عملی است به قسمت ۳ بازگرد. وگرنه جواب را با $x$ و مقدار معلوم $v$ علامت گذاری کن
4. اگر $v>v*$ و $x$ عدد صحیح بود، قرار بده $v*\leftarrow v,x*\leftarrow x$ و به ۳ بازگرد
5. اگر $v\leq v*$ ، به ۳ بازگرد
6. اگر مطلوب بود جستجو کن برای سطوح برشی که توسط $x$ نقض می‌شوند. اگر پیدا شد آن‌ها را به جواب اضافه کن و بازگرد به ۳٫۲
7. شاخه بزن برای قسمت کردن مسئله به مسائل جدید با مناطق ممکن محدود. این مسائل را به $L$ اضافه کن و به ۳ بازگرد
بازگردان $x*$

راهبردهای شاخه شدن

یک مرحلهٔ مهم در الگوریتم شاخه و حد مرحلهٔ شاخه شدن است. در این مرحله انواع مختلفی از شاخه شدن‌های ابتکاری وجود دارد که می‌توان از آن‌ها استفاده کرد. تمامی استراتژی‌های شاخه شدنی که در زیر توضیح داده شده‌اند شامل موردی هستند به نام شاخه شدن بر روی متغیر.^[۲] شاخه شدن بر روی متغیر شامل انتخاب یک متغیر، $x_{i}$ ، و مقدار کسری $x_{i}'$ برای جواب راحتی lp کنونی و سپس اضافه کردن قیود $x_{i}\leq \lfloor x_{i}'\rfloor$ و $x_{i}\geq \lceil x_{i}'\rceil$ است.

غیر عملی‌ترین شاخه شدن این استراتژی متغیری را انتخاب می‌کند که قسمت کسری آن به ۰٫۵ نزدیک است.
شاخه شدن شبه هزینه ایدهٔ اصلی این استراتژی نگه داشتن تغییر در تابع هدف برای هر متغیر $x_{i}$ ، زمانی که قبلاً به عنوان متغیری که شاخه شدن بر روی آن انجام شده انتخاب شده‌است. پس این استراتژی متغیری را انتخاب می‌کند که پیش‌بینی می‌شود بیشترین تغییر را در تابع هدف خواهد داشت، بر اساس تغییرات گذشته که به عنوان متغیر شاخه شدن انتخاب شده‌است. لازم به ذکر است که این روش اساساً در جستجو بی ارزش است چراکه تعداد کمی از متغیرها بر روی آن‌ها شاخه زده می‌شود.
شاخه زدن قوی این روش شامل آزمایش است که کدام یک از متغیرهای کاندید بیشترین پیشرفت را در تابع هدف ایجاد می‌کند قبل از آنکه واقعاً بر روی آن‌ها شاخه زده شود. شاخه زدن قوی کامل، همهٔ متغیرهای کاندید را آزمایش می‌کند و از نظر محاسباتی می‌تواند پرهزینه باشد. هزینهٔ محساباتی می‌تواند با در نظر گرفتن تنها زیر مجموعه‌ای از متغیرهای کاندید کاهش یابد به جای آنکه هر یک از راحتی‌های lpهای متناظر تا انتها حل شوند.

همچنین تعداد زیادی از گونه‌های این استراتژی‌های شاخه شدن وجود دارد. به عنوان مثال زمانی که شاخه شدن شبه هزینه نسبتاً بی ارزش است ابتدا از شاخه شدن قوی استفاده کرد سپس بعداً از شاخه شدن شبه هزینه استفاده کرد زمانی که به اندازهٔ کافی تاریخچهٔ شاخه کردن موجود باشد تا این روش مؤثر واقع شود.

پیوند به بیرون

Mixed Integer Programming
BranchAndCut.org FAQ
SCIP an open source framework for branch-cut-and-price and a mixed integer programming solver
ABACUS - A Branch-And-CUt System - open source software
COIN-OR Cbc - open source software

منابع

↑ John E., Mitchell (2002). "Branch-and-Cut Algorithms for Combinatorial Optimization Problems". Handbook of Applied Optimization: ۶۵–۷۷.
↑ Achterberg, T. (2005). "Branching rules revisited". Operations Research. ۳۳ (۱): ۴۲–۵۴. {{cite journal}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)

[1] John E., Mitchell (2002). "Branch-and-Cut Algorithms for Combinatorial Optimization Problems". Handbook of Applied Optimization: ۶۵–۷۷.

[2] Achterberg, T. (2005). "Branching rules revisited". Operations Research. ۳۳ (۱): ۴۲–۵۴. {{cite journal}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)

[۱]

[۲]