الگوریتم انشعاب و کران (Branch and Bound)
- معرفیشده توسط
- Ailsa Land & Alison Doig
- سال
- 1960
- نوع
- Exact combinatorial optimization algorithm
- خانواده
- Mathematical programming
این متن ترجمه ماشینی است و هنوز بازبینی نشده است. متن اصلی را به انگلیسی بخوانید
چه کاری انجام میدهد؟
انشعاب و کران یک الگوریتم دقیق و سیستماتیک برای مسائل بهینهسازی ترکیبیاتی و صحیح است که در سال ۱۹۶۰ توسط آیلسا لند و آلیسون دایگ معرفی شد. این الگوریتم فضای جستجو را به صورت درختی از زیرمسائل سازماندهی میکند، از کرانهای بالایی مشتقشده از رخسازی (relaxation) برای هرس کردن شاخههایی که نمیتوانند بهترین راهحل شناختهشده را بهبود بخشند، استفاده میکند و تضمین میکند که یک راهحل صحیح بهینه سراسری پیدا شود. این الگوریتم ستون فقرات حلکنندههای مدرن برنامهریزی عدد صحیح مختلط (mixed-integer programming) است که در تحقیق در عملیات، لجستیک، زمانبندی و طراحی مهندسی به کار میروند.
شهود پشت روش
تصور کنید در حال جستجو برای یافتن بالاترین ارزش کالای پنهانشده در یک هزارتوی وسیع از اتاقها هستید. به جای بررسی هر اتاق، حداکثر ارزش ممکن قابل دستیابی از هر راهرو را قبل از ورود به آن تخمین میزنید. اگر این سقف پایینتر از بهترین کالایی باشد که از قبل در اختیار دارید، کل راهرو را بدون ورود به آن نادیده میگیرید. انشعاب و کران به همین ترتیب عمل میکند: مسئله را به قطعات کوچکتر تقسیم میکند، کرانهای بالایی خوشبینانه برای هر قطعه محاسبه میکند و هر قطعهای را که اثباتاً نمیتواند از بهترین راهحل فعلی بهتر باشد، بلافاصله دور میاندازد.
تاریخ
لند و دایگ مقاله بنیادی انشعاب و کران را در سال ۱۹۶۰ در مجله Econometrica منتشر کردند و آن را بهعنوان یک روش خودکار برای برنامهریزی گسسته معرفی نمودند. لیتل و همکاران (۱۹۶۳) این تکنیک را برای مسئله فروشنده دورهگرد به کار بردند و نقش آن را در بهینهسازی ترکیبیاتی تثبیت کردند. داکین (۱۹۶۵) انشعاب مبتنی بر رخسازی خطی را معرفی کرد که رایجترین شکل امروزی است. دهههای بعدی شاهد ادغام صفحات برش (branch-and-cut) و تولید ستون (branch-and-price) بود که انشعاب و کران را به موتور محرکه تمام حلکنندههای اصلی برنامهریزی صحیح تجاری تبدیل کرد.
چه زمانی استفاده شود
هنگامی از انشعاب و کران استفاده کنید که باید راهحل اثباتشده بهینه را برای یک برنامه خطی صحیح مختلط یا صحیح خالص پیدا کنید و نمیتوانید پاسخی تقریبی را بپذیرید. این روش فرض میکند که مسئله را میتوان با رخسازیهای خطی (یا محدب) که کرانهای مفیدی ارائه میدهند، فرمولبندی کرد. این روش برای نمونههای بسیار بزرگ که درخت شمارش منفجر میشود، برای برنامههای صحیح غیرخطی بدون رخسازیهای تنگ، یا برای تنظیمات بلادرنگ که زمان محاسبات بهشدت محدود است، کمتر مناسب است. در چنین مواردی، ممکن است هیوریستیکها یا فرا-هیوریستیکها ترجیح داده شوند.
محدودیتها و ملاحظات
- پیچیدگی بدترین حالت نمایی است؛ در نمونههای با ساختار ضعیف، درخت میتواند بهطور غیرقابل تحملی بزرگ شود.
- عملکرد بهشدت به انتخاب متغیر انشعاب و استراتژی انتخاب گره حساس است.
- نیاز به یک رخسازی قابل مدیریت دارد که کرانهای بالای معنیداری ارائه دهد؛ کرانهای ضعیف منجر به هرس حداقل میشوند.
- الزامات حافظه میتواند قابل توجه باشد زمانی که بسیاری از گرههای باز باید بهطور همزمان ذخیره شوند.
شرایط منبع جایگزین بررسی علمی مستقل یا اعتبارسنجی توسط موتور تحلیل نیست.
نقاط قوت
- بهینگی سراسری را برای برنامههای صحیح و ترکیبیاتی تضمین میکند.
- جستجو را از طریق هرس مبتنی بر کران بهطور چشمگیری کاهش میدهد - اغلب تنها بخش کوچکی از درخت شمارش کامل کاوش میشود.
- انعطافپذیر: میتواند صفحات برش (branch-and-cut) یا کرانهای هیوریستیک (branch-and-price) را برای کارایی بیشتر ادغام کند.
- بهطور گسترده در حلکنندههای تجاری بالغ (CPLEX, Gurobi) و ابزارهای متنباز (GLPK, CBC) پیادهسازی شده است.
کاربردها
- زمانبندی خدمه هواپیما و تخصیص ناوگان در تحقیق در عملیات.
- طراحی شبکه زنجیره تأمین و مسائل مکانیابی تأسیسات.
- چیدمان مدارات VLSI و تخصیص رجیستر در مهندسی کامپیوتر.
- پیشبینی ساختار پروتئین و مونتاژ ژنوم در زیستشناسی محاسباتی.
- بهینهسازی پرتفوی مالی با محدودیتهای کاردینالیتی.
چگونه کار میکند
چگونه کار میکند
الگوریتم با حل کردن یک نسخه رخسازیشده (relaxed version) از مسئله - معمولاً رخسازی خطی (LP relaxation) - که محدودیتهای صحیح بودن (integrality constraints) را نادیده میگیرد، آغاز میشود. این رخسازی یک کران بالا بر روی مقدار بهینه واقعی ارائه میدهد، زیرا هر راهحل صحیح شدنی (feasible integer solution) در رخسازی نیز شدنی است. اگر راهحل رخسازیشده بهصورت عدد صحیح باشد، مسئله بلافاصله حل میشود.
فرمول
\text{Solve LP relaxation: } z^* = \max\{\mathbf{c}^\top \mathbf{x} \mid A\mathbf{x} \leq \mathbf{b},\, \mathbf{x} \geq 0\}هنگامی که راهحل رخسازیشده شامل یک متغیر کسری است، الگوریتم ناحیه شدنی را با افزودن محدودیتهای مکمل که متغیر را مجبور به گرفتن مقدار کف (floor) یا سقف (ceiling) خود میکنند، تقسیم میکند. هر تقسیمبندی یک گره فرزند جدید در درخت جستجو ایجاد میکند و بهطور مؤثر یک زیرمسئله را به دو زیرمسئله کوچکتر با دامنههای تنگتر تقسیم میکند.
فرمول
\text{Select fractional variable } x_j \notin \mathbb{Z}\text{; create sub-problems: } x_j \leq \lfloor x_j^* \rfloor \text{ and } x_j \geq \lceil x_j^* \rceilبه هر گره فعال، کران رخسازی خطی مخصوص به خود اختصاص داده میشود. گرهای که کران آن از بهترین راهحل صحیح یافتشده تاکنون - که رقیب (incumbent) نامیده میشود - تجاوز نمیکند، نمیتواند حاوی راهحل بهتری باشد، بنابراین هرس میشود. کرانهای تنگ حیاتی هستند: هرچه کران تنگتر باشد، گرههای کمتری باید کاوش شوند.
فرمول
\text{Compute bound } UB_k \text{ for node } k\text{; prune if } UB_k \leq z_{\text{inc}}یک گره در سه شرط خاتمه مییابد (بهطور دائم بسته میشود): رخسازی آن شدنی نیست، کران آن بهتر از رقیب نیست، یا راهحل رخسازیشده آن از قبل صحیح-شدنی (integer-feasible) است. در حالت اخیر، اگر راهحل جدید رقیب را بهبود بخشد، رقیب بهروزرسانی میشود. الگوریتم زمانی خاتمه مییابد که تمام گرهها خاتمه یافته باشند، در این نقطه رقیب، بهینه سراسری است.
فرمول
\text{Fathom node } k \text{ if infeasible, or } UB_k \leq z_{\text{inc}}, \text{ or } \mathbf{x}^*_k \in \mathbb{Z}^n\text{; update } z_{\text{inc}} \leftarrow \max(z_{\text{inc}}, z_k)دامهای رایج
- انتخاب ضعیف متغیر انشعاب (مثلاً همیشه انشعاب بر روی اولین متغیر کسری) اغلب منجر به درختهای عمیق و نامتعادل و همگرایی کند میشود.
- نادیده گرفتن نامساویهای معتبر (صفحات برش) به معنای از دست دادن فرصت برای تنگ کردن کرانهای رخسازی بهطور قابل توجه است.
- خاتمه زودهنگام با شکاف زیربهینگی که بهاینصورت گزارش نمیشود، میتواند تمرینکنندگان را گمراه کند تا یک راهحل نزدیک به بهینه را بهاشتباه راهحل دقیق در نظر بگیرند.
- اعمال انشعاب و کران بر روی رخسازیهای غیرخطی یا غیرمحدب بدون تحدبسازی تخصصی ممکن است کرانهای نامعتبر و نتایج نادرست ایجاد کند.
پرسشهای متداول
انشعاب و کران چگونه با شمارش جامع (exhaustive enumeration) تفاوت دارد؟
شمارش جامع هر راهحل صحیح شدنی را بهطور صریح ارزیابی میکند که برای مسائل بزرگ از نظر محاسباتی شدنی نیست. انشعاب و کران با محاسبه کرانهای بالای مبتنی بر رخسازی در هر گره از درخت جستجو و هرس کردن کل زیردرختها هرگاه کران نتواند از بهترین راهحل یافتشده قبلی فراتر رود، از این امر اجتناب میکند. در عمل، تنها بخش کوچکی از درخت هرگز مورد بررسی قرار نمیگیرد.
نقش رخسازی خطی در انشعاب و کران چیست؟
رخسازی خطی محدودیتهای صحیح بودن را حذف میکند و مسئله را میتوان در زمان چندجملهای با استفاده از روش سیمپلکس یا نقطه درونی حل کرد. مقدار بهینه آن بهعنوان یک کران بالا برای زیرمسئله صحیح متناظر عمل میکند. هنگامی که این کران تنگ است - نزدیک به بهینه صحیح واقعی - نیاز به کاوش شاخههای کمتری است. رخسازیهای تنگتر، که اغلب با افزودن نامساویهای معتبر به دست میآیند، بهطور چشمگیری الگوریتم کلی را تسریع میکنند.
چه زمانی باید از انشعاب و کران در مقابل فرا-هیوریستیکهایی مانند الگوریتمهای ژنتیک استفاده کنم؟
هنگامی که به گواهی بهینگی نیاز دارید و میتوانید زمان محاسبات را تحمل کنید، انشعاب و کران را انتخاب کنید. این روش برای مسائل با اندازه متوسط با رخسازیهای خطی با ساختار خوب ایدهآل است. فرا-هیوریستیکها زمانی ترجیح داده میشوند که مسئله بسیار بزرگ باشد، فاقد رخسازی مفید باشد، یا باید در یک بودجه زمانی محدود حل شود که یک راهحل نزدیک به بهینه قابل قبول است. بسیاری از تمرینکنندگان هر دو را ترکیب میکنند: از انشعاب و کران با تحمل شکاف خاتمه زودهنگام استفاده کنید.
روشهای مرتبط
منابع
Land, A. H., & Doig, A. G. (1960). An automatic method of solving discrete programming problems. Econometrica, 28(3), 497–520.
باز کردن مرجع DOIکپی شد.