مقایسهٔ روش‌های بهینه‌سازی برای جداسازی مجموعه‌های قرمز و آبی

پژوهشگران مسئلهٔ «حداقل مجموعهٔ جداکنندهٔ قرمزـآبی» (MRBSSP) را که از هندسهٔ محاسباتی می‌آید، بررسی کرده‌اند. آن‌ها یک صورت‌بندی فشردهٔ Set-Cover مبتنی بر برنامه‌ریزی خطی عددصحیح (ILP)، قواعد پیش‌پردازش امن، روش ابتکاری GRASP و دو رویکرد دقیق پیشنهاد داده‌اند: تجزیهٔ مبتنی بر منطق Benders (LBBD) و روش Branch-and-Benders-Cut (BBC).

این روش‌ها با ILP و دو روش پیشین، GRASP و جست‌وجوی همسایگی متغیر (VNS)، مقایسه شدند. آزمایش‌ها روی ۲۵۰ گراف تصادفی با حداکثر ۵۰۰ رأس انجام شد. بر اساس چکیدهٔ مقاله، ILP بهترین جواب‌های شدنی را به دست آورد؛ LBBD نیز قوی‌ترین کران‌های پایین و کمترین میانگین فاصله از جواب بهینه را ارائه کرد. منبع در بخش در دسترس، نتیجهٔ مقایسه دربارهٔ BBC را بیان نمی‌کند.