شاخه و برش

شاخه و برش ( Branch and cut ) روشی است در بهینه سازی ترکیبیاتی برای حل مسائل برنامه های خطی عدد صحیح، این مسائل، برنامه نویسی خطی هستند که در آن ها برخی یا همهٔ مجهولات به مقادیر اعداد صحیح محدود اند. [ ۱] شاخه و برش شامل اجرای یک الگوریتم شاخه و حد، و استفاده از سطح برش به منظور محدود کردن راحتی relaxation در برنامه نویسی خطی است. لازم به ذکر است که اگر برش ها تنها به منظور محدود کردن راحتی اولیه برنامه نویسی خطی مورد استفاده قرار گیرند؛ الگوریتم برش و شاخه نامیده می شود.
این روش برنامه های خطی بدون قید اعداد صحیح را با استفاده از الگوریتم غیر مرکب معمولی حل می کند. زمانی که یک راه حل بهینه پیدا شد، و این راه حل یک مقدار غیر صحیح برای متغیری که قرار بود مقدارش صحیح باشد داشت؛ برای یافتن قیود خطی بیشتر که توسط تمام نقاط صحیح ممکن ارضا شوند ولی به وسیله جواب کسری حاضر نقض شوند ممکن است از الگوریتم سطح برش استفاده شود. این نامساوی ها ممکن است به برنامه خطی اضافه شوند، به طوری که دوباره حل کردن آن به جوابی متفاوت منجر خواهد شد که اگر امیدوار باشیم «کمتر کسری» است.
در این نقطه، بخش شاخه و حد الگوریتم آغاز شده است. مسئله به چندین ( معمولاً دو ) نسخه تقسیم می شود. برنامه های خطی جدید به وسیلهٔ روش غیر مرکب حل می شوند و فرایند تکرار می شود. در طول فرایند شاخه و حد، جواب های غیر انتگرالی برای، راحتی برنامه نویسی خطی، به عنوان حد بالا به کار گرفته می شوند و جواب های انتگرالی به عنوان حد پایین. یک گره می تواند هرس شود اگر یک حد بالا، پایین تر از حد پایین موجود باشد. همچنین در هنگام حل راحتی lp ممکن است سطح برش اضافی تولید گردد، که یا برش های سراسری هستند به عنوان مثال معتبر برای تمام جواب های صحیح، ویا برش های محلی، به آن معنی که آن ها به وسیلهٔ تمامی جوابهایی که قیود جانبی زیر درخت شاخه و حد در نظر گرفته شدهٔ کنونی را برآورده می کنند، ارضا می شوند.
الگوریتم به صورت زیر خلاصه شده است. الگوریتم فرض می کند ILP ( برنامه نویسی منطقی استقرایی ) یک مسئلهٔ بیشینه سازی است.
• افزودن ILP اولیه به L، لیست مسائل فعال
• قرار دادن x ∗ = null {\displaystyle x*={\text{null}}} و v ∗ = − ∞ {\displaystyle v*= - \infty }
• تا زمانی که L {\displaystyle L} خالی نیست
• انتخاب و حذف یک مسئله از L {\displaystyle L}
• حل Relaxation مسئله
• اگر جواب مسئله غیر عملی است به قسمت ۳ بازگرد. وگرنه جواب را با x {\displaystyle x} و مقدار معلوم v {\displaystyle v} علامت گذاری کن
• اگر v > v ∗ {\displaystyle v> v*} و x {\displaystyle x} عدد صحیح بود، قرار بده v ∗ ← v , x ∗ ← x {\displaystyle v*\leftarrow v, x*\leftarrow x} و به ۳ بازگرد
• اگر v ≤ v ∗ {\displaystyle v\leq v*} ، به ۳ بازگرد
• اگر مطلوب بود جستجو کن برای سطوح برشی که توسط x {\displaystyle x} نقض می شوند. اگر پیدا شد آن ها را به جواب اضافه کن و بازگرد به ۳٫۲
• شاخه بزن برای قسمت کردن مسئله به مسائل جدید با مناطق ممکن محدود. این مسائل را به L {\displaystyle L} اضافه کن و به ۳ بازگرد