تجزیهٔ بندرز با زیرمسئلهٔ عددصحیح

نویسندگان: Ashkan Fakhri، Mehdi Ghatee، Antonios Fragkogios و Georgios K.D.Saharidis

منتشرشده در: Expert Systems with Applications، جلد 89، 15 دسامبر 2017، صفحات 20–30.

چکیده:

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

نکات برجسته:

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