محدودیت های تنبل در CPLEX


بسته به شرایط فضای شدنی و تابع هدف، محدودیت‌ها عملکردهای متفاوتی از خود نشان می‌دهند: محدودیت‌های کارکردی، غیرکارکردی، الزام‌آور، غیرالزام‌آور، فعال، زائد و غیره. محدودیت‌های دیگری نیز در این فضا قابل ارائه است که برخی از خواص محدودیت‌های سنتی را دارا هستند: هم الزام‌آور و هم غیرالزام‌آور. جای تعجب نیست که چنین محدودیت‌هایی در علم بهینه‌سازی محاسباتی نقش‌آفرینی می‌کنند. یک دسته از این محدودیت‌ها به محدودیت‌های تنبل lazy constraints مشهور هستند. در این پست قصد داریم این دسته محدودیت‌ها را معرفی و با ویژگی‌ها و کارکردهای آن در نرم‌افزار CPLEX آشنا شویم.

قبل از اینکه سراغ مفهوم محدودیت‌های تنبل و کارکرد آن‌ها در نرم‌افزار CPLEX برویم، ابتدا مفهوم برش‌ها cuts به‌عنوان یک دسته محدودیت بررسی می‌نماییم.

 یک برش محدودیتی بوده که جز مسئله اصلی نبوده و مجاز به حذف هیچ قسمتی از فضای شدنی (شامل جواب‌های عدد صحیح) نیست. برش‌ها اغلب به دو علت به مسئله اضافه می‌شوند:

۱- جهت تفکیک یک گره در درخت جستجو به دو گره با زیرمساله‌ی کوچک‌تر
۲- جهت تقویت کران‌ها با حذف بخش‌های زائد پوسته پیوسته LP hull

قبل از اینکه بحث را توسعه دهیم لازم است شفاف‌سازی در خصوص پوسته پیوسته و پوسته گسسته IP hull صورت گیرد. در نمودار شکل بالا به دو چندوجهی کران‌دار که توسط دو محور عمودی و افقی محصور شده است توجه فرمایید. چندوجهی با رنگ مشکی، فضای شدنی رهاشده خطی را نشان می‌دهد. به این فضا (چندوجهی) پوسته پیوسته گفته می‌شود. به همین ترتیب چندوجهی با رنگ آبی، فضای شدنی یک مسئله برنامه‌ریزی عدد صحیح را نشان می‌دهد. این چندوجهی که حاصل از اتصال نقاط مرزی شبکه اعداد صحیح integer lattice است، به پوسته گسسته مشهور است. واضح است که پوسته گسسته زیرمجموعه‌ای از پوسته‌ی پیوسته است.

نرم‌افزار CPLEX به‌صورت خودکار انواع مختلفی از برش‌‌ها را به مسئله اضافه می‌کند. یکی از معروف‌ترین آن‌ها به برش گوموری Gomory cut مشهور است. کاربر علاوه بر این برش‌ها، می‌تواند برش‌های دیگری تعریف و در حین فرایند حل به مسئله اضافه نماید. هیچ برشی اجازه حذف قسمتی از پوسته گسسته را ندارد.

برخلاف برش‌های رایج، محدودیت‌های تنبل اجازه‌ی برش قسمتی از پوسته‌ی گسسته را دارند.

همان‌طور که در نمودار شکل بالا پیداست سه نقطه صحیح از فضای شدنی حذف گردیده‌اند. در حقیقت اگر این محدودیت به نحو درستی انتخاب شده باشد، فضای حاصل‌شده فضایی است که قصد داریم بهینه کنیم. حال سؤالی که باید پاسخ داده شود این است که کاربرد این محدودیت‌های تنبل چیست؟ سه دلیل عمده برای به‌کارگیری آن‌ها می‌توان متصور شد:

۱- اغلب مسائل واقعی برنامه‌ریزی عدد صحیح شامل تعداد بسیار زیادی محدودیت بوده که با توجه به تابع هدف، تعداد قابل‌توجهی از آن‌ها زائد بوده یا در مجاور نقطه بهینه الزام‌آور نباشند. درصورتی‌که مدل‌ساز از قبل این محدودیت‌ها را شناسایی نماید به سادگی با حذف آن‌ها کمک شایانی در سرعت بهینه‌سازی مدل خواهد کرد. لذا در اکثر مواقع شناسایی آن‌ها در ابتدای فرایند حل امری محال است. اغلب نرم‌افزارهای مدرن بهینه‌سازی به کاربر این اجازه را می‌دهند که بخشی از این محدودیت‌هایی که جز مسئله‌ی اصلی نیستند در حوضچه محدودیت‌های تنبل قرار دهد. در حین فرایند حل، نرم‌افزار نقض محدودیت‌های تنبل را بررسی کرده و در صورت نقض، آن‌ها را در مجموعه فعال قرار می‌دهد. برعکس محدودیت‌های تنبلی که به مجموعه فعال وارد شده و الزام‌آور نیستند به حوضچه محدودیت‌های تنبل ارسال می‌شوند. این امر تلاشی است در جهت کاهش زمان حل و مدیریت بهتر حافظه.
۲- دلیل دوم شاید در برخی مسائل تولید محدودیت‌ها در ابتدای فرایند حل امری بسیار هزینه‌بر است. به‌عنوان‌مثال مسئله فروشنده دوره‌گرد با محدودیت‌های حذف تور را در نظر بگیرید. تعداد محدودیت‌ها با افزایش تعداد گره‌ها (شهرها) رشد نمایی خواهد داشت. در این حالت، گزینه پیشنهادی این است که محدودیت‌های حذف تور را به‌عنوان محدودیت‌های تنبل و بسته به فرایند حل اضافه کرده و در صورت عدم کارایی حذف نماییم.
۳- برش‌های شدنی و بهینه‌ی فرایند حل تجزیه بندرز benders decomposition را نیز می‌توان به‌عنوان محدودیت‌های تنبل در نظر گرفت.

0 Comments
Inline Feedbacks
View all comments