معرفی متودولوژی برنامه ریزی محدودیت Constraint Programming

متدولوژی برنامه‌ریزی محدودیت Constraint Programming یا CP، یک فناوری ارضای محدودیت‌ها Constraint Satisfaction است که سابقه‌ی آن به علوم کامپیوتر، برنامه‌ریزی منطقی، تئوری گراف و هوش مصنوعی بر می‌گردد. CP راهکاری موثر و کارا جهت حل و بهینه‌سازی مسایلی که طبیعت ‌آنها تا حدی نامنظم هستند و نمی‌توان آن‌ها را به زبان ریاضی مدل‌سازی کرد. این مسایل شامل پنجره‌های زمانی، مسایل زمان‌بندی و تخصیص یا تعویض عملیات است.

بیشتر بخوانید

رفع مشکل تحدب در مسایل درجه دو در نرم‌افزار IBM Ilog CPLEX

در این پست قصد داریم یکی از خطاهای مهمی که کاربران به دلیل مشکلات تحدب به آن دچار می‌شوند را بررسی و راهکارهایی برای رفع آن ارائه دهیم.

CPLEX Error 5002: Q in objective is not positive semi-definite (psd)

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

بیشتر بخوانید

آشنایی با برنامه ریزی هندسی

معرفی و شمای کلی

نظریه برنامه‌ریزی هندسی (Geometric Programming) یا به اختصار GP در سال‌های ۱۹۶۱ الی ۱۹۶۷ توسط فیزیکدان نظری آقای زنر (Clarence Zener) مطرح گردید. هدف از این کار ارائه راهکار مطمئن برای حل مسایل غیرخطی با ساختارهای مشخص بود. متعاقبا در سال‌های بعدی آقای دافین (Richard Duffin) نظریه دوگان را برای حل مسایل غیرخطی در قالب برنامه‌ریزی هندسی ارائه کرد. از طرفی مشخصه‌های ساختاری مسایل برنامه‌ریزی هندسی، محققان و متخصصین حوزه بهینه‌سازی را به سمت طراحی الگوریتم‌های کارا مانند روش نقطه داخلی برای حل این دسته مسایل سوق داده است. به طور کلی مسایل GP دسته‌ی متمایزی از مسایل بهینه‌سازی در مجموعه‌ی برنامه‌ریزی محدب (Convex Programming) هستند.

بیشتر بخوانید

نحوه شناسایی تک کالبدی بودن ضرایب فنی

به ماتریس مربعی که دارای عناصر عدد صحیح ۰ یا ۱- یا ۱+ و دترمینان ۱- یا ۱ باشه، ماتریس تک کالبدی (unimodular matrix) گفته می‌شود. از طرفی، ماتریس کاملا تک کالبدی (totally unimodular) ماتریسی است که تمامی زیرماتریس‌های مربعی آن معکوس‌پذیر و تک کالبدی باشند. به عبارتی در صورتی که یک ماتریس ۸×۸ داشته باشیم، بایستی ۲۰۴ زیرماتریس آن را به لحاظ تک کالبدی بودن بررسی نماییم.
مزیت عمده این خاصیت این است که در برنامه ریزی تمام عدد صحیح، در صورتی که ماتریس ضرایب فنی دارای خاصیت کاملا تک‌کالبدی باشند، در اینصورت جواب‌های رهاشده خطی مساله عدد صحیح، همان جواب‌های مساله اصلی خواهند بود (تمامی متغیرها مقادیر صحیح می گیرند). به بیان دگر، پوسته محدب تمامی نقاط گوشه‌ای آن صحیح خواهند بود. برای بررسی کاملا تک‌کالبدی بودن یک برنامه‌ریزی عدد صحیح کافی است ماتریس ضرایب فنی آن را استخراج و تحلیل کرد.

بیشتر بخوانید

آشنایی با برنامه ریزی مخروطی درجه دوم

رده خاصی از مسائل غیرخطی، جز دسته مسائل برنامه ریزی مخروطی درجه دوم (second order conic programs) قرار می‌گیرند که در زمینه‌های متعدد علوم کنترل، سرمایه‌گذاری، علوم مهندسی و پزشکی و عیره کاربرد دارند. امروزه با پیشرفت علوم رایانشی، این دسته مسایل با استفاده از الگوریتم‌های تخصصی نقطه درونی (interior point) که در اکثر نرم‌افزارهای تجاری توسعه داده شده‌اند قابل حل هستند.

 

بیشتر بخوانید

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

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

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

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

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

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

 

سه راهکار عمده جهت رفع خطای کمبود حافظه در نرم افزار CPLEX

در پست قبلی اشاره شد که چه عواملی منجر به ایجاد خطای کمبود حافظه (out of memory) در نرم افزار IBM Ilog CPLEX می‌شود. در این پست سه راهکار عمده جهت برطرف‌سازی این خطا را بررسی می کنیم. اولین و ساده‌ترین راهکار ممکن تغییر پارامتر thread به مقدار ۱ است. برای این منظور کافی است که یک بلوک پیش‌پردازنده‌ی execute به صورت زیر در ابتدای کد قرار داده شود.

execute {
 cplex.threads = 1;
}

با انجام این عمل، پردازش از حالت موازی خارج شده و جستجو به صورت تک نخی (single threading) صورت می‌گیرد. در این حالت به حجم حوضچه‌ی جواب (solution pool) کمتری نیاز خواهد بود.

راهکار بعدی اجازه دسترسی به مقدار بیشتری از حافظه موقت (RAM) هست. در حالت عادی نرم افزار تنها اجازه‌ی دسترسی به ۲ گیگابایت از فضای موقت را دارد.

execute {
 cplex.workmem = 4000;
}

راهکار سوم تغییر پارامتر‌های الگوریتم حل است که اغلب با سعی و خطا همراه می‌شود. به عنوان مثال تغییر پارامتر lpmethod از مقدار یک به دو، نوع الگوریتم حل را از سیمپلکس عادی به الگوریتم سیمپلکس-دوال تغییر می دهد. در عمل ثابت شده است که الگوریتم‌های سیمپلکس-دوال نسبت به سایر الگوریتم‌های برنامه‌ریزی خطی، در حین اجرا فضای کمتری را اشغال می‌کنند.

execute {
 cplex.lpmethod = 1;
}

خطای کمبود حافظه در CPLEX چه زمانی رخ می دهد؟

یکی از پارامترهای مهم مدیریت کدهای توسعه داده‌شده در نرم‌افزار CPLEX، مدیریت حافظه آنها است. یکی از خطاهای عمده که معمولا در مدل‌های با مقیاس بالا ممکن است رخ می‌دهد، خطای حافظه‌ی خارج از دسترسی (out of memory) است.

دلیل اصلی بروز این مشکل عدم توانایی نرم‌افزار در کنترل انباشت اطلاعات در تکرارهای مختلف است و در نهایت رشد نمایی داده‌ها دامن زده می‌شود. رشد نمایی داده‌ها اغلب در مدل‌های برنامه‌ریزی عدد صحیح مورد توجه می‌باشد؛ بدین ترتیب مدیریت شاخه‌های بسته نشده (unfathomed) نقش بسیار موثری در کاهش حافظه موقت ایفا خواهند کرد.

از طرفی زبان های سطح بالا مانند سی شارپ و جاوا به طور خودکار از قابلیت مدیریت حافظه پشتیبانی می‌کنند. به عبارتی اگر متغیر محلی برای ادامه‌ی برنامه مفید نباشد، مفسر بار مدیریت حافظه رو به دوش کشیده و با استفاده از خاصیت garbage collecting متغیرهای غیرضروری را جهت آزادسازی فضای حافظه‌ی موقت (RAM) حذف می‌نماید. در نرم افزار IBM Ilog CPLEX نیز روندی مشابه را شاهد هستیم. بخش profiler در این نرم‌افزار، مسئول نظارت بر مدیریت صحیح حافظه می‌باشد.

اغلب مواقع راه حل اصلی این است که بخشی از مدل یا داده‌های مدل سازمان‌دهی مجدد (restructure) شوند؛ به‌عبارتی جهت فشرده‌سازی داده‌ها و بهره‌برداری موثر از حافظه، توصیه می‌شود از ساختارهای داده (data structure) یا مجموعه های مرتب (tuple) بهره گرفته شود.

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

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

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

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

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