موضوع مقاله: شاخه و برش | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # شاخه و برش | مقدمه: شاخه و برش (Branch and cut) روشی است در بهینه سازی ترکیبیاتی برای حل مسائل برنامه‌های خطی عدد صحیح، این مسائل، برنامه نویسی خطی هستند که در آن‌ها برخی یا همهٔ مجهولات به مقادیر اعداد صحیح محدود‌اند. | ## بخش 1: شاخه و برش | شاخه و برش شامل اجرای یک الگوریتم شاخه و حد، و استفاده از سطح برش به منظور محدود کردن راحتی relaxation در برنامه‌نویسی خطی است. لازم به ذکر است که اگر برش‌ها تنها به منظور محدود کردن راحتی اولیه برنامه نویسی خطی مورد استفاده قرار گیرند؛ الگوریتم برش و شاخه نامیده می‌شود. شرح الگوریتم این روش برنامه‌های خطی بدون قید اعداد صحیح را با استفاده از الگوریتم غیر مرکب معمولی حل می‌کند. زمانی که یک راه حل بهینه پیدا شد، و این راه حل یک مقدار غیر صحیح برای متغیری که قرار بود مقدارش صحیح باشد داشت؛ برای یافتن قیود خطی بیشتر که توسط تمام نقاط صحیح ممکن ارضا شوند ولی به وسیله جواب کسری حاضر نقض شوند ممکن است از الگوریتم سطح برش استفاده شود. این نامساوی‌ها ممکن است به برنامه خطی اضافه شوند، به طوری که دوباره حل کردن آن به جوابی متفاوت منجر خواهد شد که اگر امیدوار باشیم «کمتر کسری» است. در طول فرایند شاخه و حد، جواب‌های غیر انتگرالی برای، راحتی برنامه نویسی خطی، به عنوان حد بالا به کار گرفته می‌شوند و جواب‌های انتگرالی به عنوان حد پایین. همچنین در هنگام حل راحتی lp ممکن است سطح برش اضافی تولید گردد، که یا برش‌های سراسری هستند به عنوان مثال معتبر برای تمام جواب‌های صحیح، ویا برش‌های محلی، به آن معنی که آن‌ها به وسیلهٔ تمامی جوابهایی که قیود جانبی زیر درخت شاخه و حد در نظر گرفته شدهٔ کنونی را برآورده می‌کنند، ارضا می‌شوند. | ## بخش 2: شاخه و برش | الگوریتم فرض می‌کند ILP (برنامه‌نویسی منطقی استقرایی) یک مسئلهٔ بیشینه سازی است. وگرنه جواب را با و مقدار معلوم علامت گذاری کن اگر و عدد صحیح بود، قرار بده و به ۳ بازگرد اگر ، به ۳ بازگرد اگر مطلوب بود جستجو کن برای سطوح برشی که توسط نقض می‌شوند. اگر پیدا شد آن‌ها را به جواب اضافه کن و بازگرد به ۳٫۲ شاخه بزن برای قسمت کردن مسئله به مسائل جدید با مناطق ممکن محدود. این مسائل را به اضافه کن و به ۳ بازگرد بازگردان راهبردهای شاخه شدن یک مرحلهٔ مهم در الگوریتم شاخه و حد مرحلهٔ شاخه شدن است. در این مرحله انواع مختلفی از شاخه شدن‌های ابتکاری وجود دارد که می‌توان از آن‌ها استفاده کرد. تمامی استراتژی‌های شاخه شدنی که در زیر توضیح داده شده‌اند شامل موردی هستند به نام شاخه شدن بر روی متغیر. شاخه شدن بر روی متغیر شامل انتخاب یک متغیر، ، و مقدار کسری برای جواب راحتی lp کنونی و سپس اضافه کردن قیود و است. | ## بخش 3: شاخه و برش | غیر عملی‌ترین شاخه شدن این استراتژی متغیری را انتخاب می‌کند که قسمت کسری آن به ۰٫۵ نزدیک است. شاخه شدن شبه هزینه ایدهٔ اصلی این استراتژی نگه داشتن تغییر در تابع هدف برای هر متغیر ، زمانی که قبلاً به عنوان متغیری که شاخه شدن بر روی آن انجام شده انتخاب شده‌است. پس این استراتژی متغیری را انتخاب می‌کند که پیش‌بینی می‌شود بیشترین تغییر را در تابع هدف خواهد داشت، بر اساس تغییرات گذشته که به عنوان متغیر شاخه شدن انتخاب شده‌است. لازم به ذکر است که این روش اساساً در جستجو بی ارزش است چراکه تعداد کمی از متغیرها بر روی آن‌ها شاخه زده می‌شود. شاخه زدن قوی این روش شامل آزمایش است که کدام یک از متغیرهای کاندید بیشترین پیشرفت را در تابع هدف ایجاد می‌کند قبل از آنکه واقعاً بر روی آن‌ها شاخه زده شود. شاخه زدن قوی کامل، همهٔ متغیرهای کاندید را آزمایش می‌کند و از نظر محاسباتی می‌تواند پرهزینه باشد. هزینهٔ محساباتی می‌تواند با در نظر گرفتن تنها زیر مجموعه‌ای از متغیرهای کاندید کاهش یابد به جای آنکه هر یک از راحتی‌های lpهای متناظر تا انتها حل شوند. | ## جمع‌بندی | به عنوان مثال زمانی که شاخه شدن شبه هزینه نسبتاً بی ارزش است ابتدا از شاخه شدن قوی استفاده کرد سپس بعداً از شاخه شدن شبه هزینه استفاده کرد زمانی که به اندازهٔ کافی تاریخچهٔ شاخه کردن موجود باشد تا این روش مؤثر واقع شود.