الگوریتم های تجزیه تا چه اندازه ای موثر هستند؟

  اکثر علاقه مندان علم تحقیق در عملیات و بهینه سازی شاید برای یک بار هم که شده کتاب آقای ویلیامز (Williams) تحت عنوان مدل‌سازی در برنامه‌ریزی ریاضی (Model building in mathematical programming) را در طول دوره تحصیل‌شان مطالعه یا شنیده باشند. بدون شک یکی از منابع ارزشمند در زمینه دانش مدل‌سازی این مرحع هست. در بخش تجزیه (decomposition) این کتاب، آقای ویلیامز شرح می دهد:

الگوریتم های تجزیه از اهمیت محاسباتی قابل توجهی برخوردار هستند به این ترتیب که این الگوریتم ها امکان حل مسایل یکپارچه را در ابعاد وسیع میسر می سازند. علی رغم این مساله،‌ روش های تجزیه با موفقیت های محاسباتی محدودی روبرو شده اند. الگوریتم دانتزیگ-ولف (Dantzig-Wolfe) محبوبیت بیشتری را در میان سایر الگوریتم های تجزیه بدست آورده است. علی رغم این محبوبیت اغلب اوقات حل مدل به صورت یکپارچه بسیار کاراتر از حل مدل توسط الگوریتم های تجزیه خواهد بود! مهمترین توصیه به شخصی که علاقه مند به تجزیه مساله مورد نظر خود و حل آن توسط یکی از روش های تجزیه می باشد اینه که این تصمیم حتما بایستی مبنای تجربی داشته باشد و صرفا جنبه تلاش-برای-حل-موثر نباشد.

بسیاری از علاقه‌مندان این روش‌ها از این موضوع شکایت دارند که ماه‌ها تلاش برای پیاده‌سازی روش‌های تجزیه همانند دانتزیگ ولف (dantzig wolf) یا بندرز (Benders) در نهایت منجر به بهبود اندکی در زمان حل و اجرای مدل شده‌اند.

پروفسور مارکو لوبکه (Marco Lübbecke) در پاسخ به این ابهام اذعان دارند که سرعت بخشی به این دسته الگوریتم‌ها دانش و مهارت‌های خاصی می‌طلبد. ایشان اشاره دارند که بسیاری از دانشجویان نسخه‌های ساده و پیش پا افتاده‌ای از این الگوریتم‌ها را بکار می‌گیرند که از عهده حل مثال‌هایی در مقیاس بزرگتر بر نخواهند آمد.

ایشان دو solver متن‌باز Dip و GCG را جهت شناسایی مشخصه‌های ساختاری مساله و پیاده‌سازی الگوریتم‌های تجزیه پیشنهاد کرده‌اند.

 

پشتیبانی CPLEX از روش های شاخه، برش و قیمت‌گذاری

با توجه به تعدد سوالات دوستان مبنی بر قابلیت‌های نرم‌افزار CPLEX در پیاده‌سازی دو الگوریتم شاخه و قیمت‌گذاری (branch&price) و شاخه و برش (branch&cut)، سه نکته مهم را بایستی خدمت این بزرگواران برسانیم:

۱- سالور cplex از الگوریتم branch&price پشتیبانی نمی‌کند. چرا؟ به این دلیل که این نرم‌افزار اجازه ایجاد متغیر جدید در حین فرایند حل را نمی‌دهد (حتی با استفاده از تکنیک‌های callbacks). توجه داشته باشیم که cplex از تکینک تولید ستون (column generation) حمایت می‌کند.

۲- هسته اصلی الگوریتم حل cplex مجهز به الگوریتم branch&cut است. همه برش‌هایی که در حین فرایند حل تولید می‌شوند در فایل option قابل سفارشی شدن هستند.

۳- سالور cplex از الگوریتم branch&cut اختصاصی پشتیبانی می‌کند. این موضوع در محیط نرم‌افزاری clplex پشتیانی نمی‌شود ولی در سایر پلتفرم‌های برنامه‌نویسی قابلیت‌های متنوعی برای اختصاصی کردن این الگوریتم وجود دارد. با استفاده از یکی از زبان‌های سطح بالا و همچنین قابلیت concert technology، می‌توان از کلاس ها و توابع UserCutCallback در این خصوص بهره گرفت.