شاخه و برش (Branch and cut) روشی است در بهینه سازی ترکیبیاتی برای حل مسائل برنامه های خطی عدد صحیح، این مسائل، برنامه نویسی خطی هستند که در آن ها برخی یا همهٔ مجهولات به مقادیر اعداد صحیح محدود اند. شاخه و برش شامل اجرای یک الگوریتم شاخه و حد، و استفاده از سطح برش به منظور محدود کردن راحتی relaxation در برنامه نویسی خطی است. لازم به ذکر است که اگر برش ها تنها به منظور محدود کردن راحتی اولیه برنامه نویسی خطی مورد استفاده قرار گیرند؛ الگوریتم برش و شاخه نامیده می شود.
غیر عملی ترین شاخه شدن این استراتژی متغیری را انتخاب می کند که قسمت کسری آن به ۰٫۵ نزدیک است.
شاخه شدن شبه هزینه ایدهٔ اصلی این استراتژی نگه داشتن تغییر در تابع هدف برای هر متغیر x i {\displaystyle x_{i}} ، زمانی که قبلاً به عنوان متغیری که شاخه شدن بر روی آن انجام شده انتخاب شده است. پس این استراتژی متغیری را انتخاب می کند که پیش بینی می شود بیشترین تغییر را در تابع هدف خواهد داشت، بر اساس تغییرات گذشته که به عنوان متغیر شاخه شدن انتخاب شده است. لازم به ذکر است که این روش اساساً در جستجو بی ارزش است چراکه تعداد کمی از متغیرها بر روی آن ها شاخه زده می شود.
شاخه زدن قوی این روش شامل آزمایش است که کدام یک از متغیرهای کاندید بیشترین پیشرفت را در تابع هدف ایجاد می کند قبل از آنکه واقعاً بر روی آن ها شاخه زده شود. شاخه زدن قوی کامل، همهٔ متغیرهای کاندید را آزمایش می کند و از نظر محاسباتی می تواند پرهزینه باشد. هزینهٔ محساباتی می تواند با در نظر گرفتن تنها زیر مجموعه ای از متغیرهای کاندید کاهش یابد به جای آنکه هر یک از راحتی های lpهای متناظر تا انتها حل شوند.
این روش برنامه های خطی بدون قید اعداد صحیح را با استفاده از الگوریتم غیر مرکب معمولی حل می کند. زمانی که یک راه حل بهینه پیدا شد، و این راه حل یک مقدار غیر صحیح برای متغیری که قرار بود مقدارش صحیح باشد داشت؛ برای یافتن قیود خطی بیشتر که توسط تمام نقاط صحیح ممکن ارضا شوند ولی به وسیله جواب کسری حاضر نقض شوند ممکن است از الگوریتم سطح برش استفاده شود. این نامساوی ها ممکن است به برنامه خطی اضافه شوند، به طوری که دوباره حل کردن آن به جوابی متفاوت منجر خواهد شد که اگر امیدوار باشیم «کمتر کسری» است.
در این نقطه، بخش شاخه و حد الگوریتم آغاز شده است. مسئله به چندین (معمولاً دو) نسخه تقسیم می شود. برنامه های خطی جدید به وسیلهٔ روش غیر مرکب حل می شوند و فرایند تکرار می شود. در طول فرایند شاخه و حد، جواب های غیر انتگرالی برای، راحتی برنامه نویسی خطی، به عنوان حد بالا به کار گرفته می شوند و جواب های انتگرالی به عنوان حد پایین. یک گره می تواند هرس شود اگر یک حد بالا، پایین تر از حد پایین موجود باشد. همچنین در هنگام حل راحتی lp ممکن است سطح برش اضافی تولید گردد، که یا برش های سراسری هستند به عنوان مثال معتبر برای تمام جواب های صحیح، ویا برش های محلی، به آن معنی که آن ها به وسیلهٔ تمامی جوابهایی که قیود جانبی زیر درخت شاخه و حد در نظر گرفته شدهٔ کنونی را برآورده می کنند، ارضا می شوند.
الگوریتم به صورت زیر خلاصه شده است. الگوریتم فرض می کند ILP (برنامه نویسی منطقی استقرایی) یک مسئلهٔ بیشینه سازی است.
غیر عملی ترین شاخه شدن این استراتژی متغیری را انتخاب می کند که قسمت کسری آن به ۰٫۵ نزدیک است.
شاخه شدن شبه هزینه ایدهٔ اصلی این استراتژی نگه داشتن تغییر در تابع هدف برای هر متغیر x i {\displaystyle x_{i}} ، زمانی که قبلاً به عنوان متغیری که شاخه شدن بر روی آن انجام شده انتخاب شده است. پس این استراتژی متغیری را انتخاب می کند که پیش بینی می شود بیشترین تغییر را در تابع هدف خواهد داشت، بر اساس تغییرات گذشته که به عنوان متغیر شاخه شدن انتخاب شده است. لازم به ذکر است که این روش اساساً در جستجو بی ارزش است چراکه تعداد کمی از متغیرها بر روی آن ها شاخه زده می شود.
شاخه زدن قوی این روش شامل آزمایش است که کدام یک از متغیرهای کاندید بیشترین پیشرفت را در تابع هدف ایجاد می کند قبل از آنکه واقعاً بر روی آن ها شاخه زده شود. شاخه زدن قوی کامل، همهٔ متغیرهای کاندید را آزمایش می کند و از نظر محاسباتی می تواند پرهزینه باشد. هزینهٔ محساباتی می تواند با در نظر گرفتن تنها زیر مجموعه ای از متغیرهای کاندید کاهش یابد به جای آنکه هر یک از راحتی های lpهای متناظر تا انتها حل شوند.
این روش برنامه های خطی بدون قید اعداد صحیح را با استفاده از الگوریتم غیر مرکب معمولی حل می کند. زمانی که یک راه حل بهینه پیدا شد، و این راه حل یک مقدار غیر صحیح برای متغیری که قرار بود مقدارش صحیح باشد داشت؛ برای یافتن قیود خطی بیشتر که توسط تمام نقاط صحیح ممکن ارضا شوند ولی به وسیله جواب کسری حاضر نقض شوند ممکن است از الگوریتم سطح برش استفاده شود. این نامساوی ها ممکن است به برنامه خطی اضافه شوند، به طوری که دوباره حل کردن آن به جوابی متفاوت منجر خواهد شد که اگر امیدوار باشیم «کمتر کسری» است.
در این نقطه، بخش شاخه و حد الگوریتم آغاز شده است. مسئله به چندین (معمولاً دو) نسخه تقسیم می شود. برنامه های خطی جدید به وسیلهٔ روش غیر مرکب حل می شوند و فرایند تکرار می شود. در طول فرایند شاخه و حد، جواب های غیر انتگرالی برای، راحتی برنامه نویسی خطی، به عنوان حد بالا به کار گرفته می شوند و جواب های انتگرالی به عنوان حد پایین. یک گره می تواند هرس شود اگر یک حد بالا، پایین تر از حد پایین موجود باشد. همچنین در هنگام حل راحتی lp ممکن است سطح برش اضافی تولید گردد، که یا برش های سراسری هستند به عنوان مثال معتبر برای تمام جواب های صحیح، ویا برش های محلی، به آن معنی که آن ها به وسیلهٔ تمامی جوابهایی که قیود جانبی زیر درخت شاخه و حد در نظر گرفته شدهٔ کنونی را برآورده می کنند، ارضا می شوند.
الگوریتم به صورت زیر خلاصه شده است. الگوریتم فرض می کند ILP (برنامه نویسی منطقی استقرایی) یک مسئلهٔ بیشینه سازی است.
wiki: شاخه و برش