مسایل برنامه‌ریزی عدد صحیح اغلب دارای جواب‌های بهینه یا شدنی چندگانه هستند و برای طراحی الگوریتم‌های کارا این جواب‌های چندگانه و ساختارهای موازی شناسایی می‌شوند. در این پست قصد داریم تعداد جواب‌های شدنی مساله‌ی مربع جادویی magic square را نه به کمک روش‌های تحلیلی بلکه به کمک نرم‌افزار CPLEX و توابع جستجوی موجود در آن، شمارش کنیم.
بسته به شرایط فضای شدنی و تابع هدف، محدودیت‌ها عملکردهای متفاوتی از خود نشان می‌دهند: محدودیت‌های کارکردی، غیرکارکردی، الزام‌آور، غیرالزام‌آور، فعال، زائد و غیره. محدودیت‌های دیگری نیز در این فضا قابل ارائه است که برخی از خواص محدودیت‌های سنتی را دارا هستند: هم الزام‌آور و هم غیرالزام‌آور. جای تعجب نیست که چنین محدودیت‌هایی در علم بهینه‌سازی محاسباتی نقش‌آفرینی می‌کنند. یک دسته از این محدودیت‌ها به محدودیت‌های تنبل lazy constraints مشهور هستند. در این پست قصد داریم این دسته محدودیت‌ها را معرفی و با ویژگی‌ها و کارکردهای آن در نرم‌افزار CPLEX آشنا شویم.
برنامه‌ریزی نیمه‌معین semi-definite programming یا به‌اختصار SDP کلاسی از بهینه‌سازی محدب convex optimization است که کاربرد آن در علم تحقیق در عملیات بسیار موفق بوده است. پوسته عدد صحیح مسائل برنامه‌ریزی عدد صحیح را می‌توان با دقت بالایی با برنامه‌ریزی نیمه معین تقریب زد. در این پست قصد داریم به مسئله حداکثر برش MAXCUT در تئوری گراف پرداخته و رهاسازی نیمه‌معین آن را با رهاسازی خطی مقایسه نماییم.
متدولوژی برنامه‌ریزی محدودیت Constraint Programming یا CP، یک فناوری ارضای محدودیت‌ها Constraint Satisfaction است که سابقه‌ی آن به علوم کامپیوتر، برنامه‌ریزی منطقی، تئوری گراف و هوش مصنوعی بر می‌گردد. CP راهکاری موثر و کارا جهت حل و بهینه‌سازی مسایلی که طبیعت آنها تا حدی نامنظم هستند و نمی‌توان آنها را به زبان ریاضی مدل‌سازی کرد. این مسایل شامل پنجره‌های زمانی، مسایل زمان‌بندی و تخصیص یا تعویض عملیات است.
به ماتریس مربعی که دارای عناصر عدد صحیح ۰ یا ۱- یا ۱+ و دترمینان ۱- یا ۱ باشه، ماتریس تک کالبدی (unimodular matrix) گفته می‌شود. از طرفی، ماتریس کاملا تک کالبدی (totally unimodular) ماتریسی است که تمامی زیرماتریس‌های مربعی آن معکوس‌پذیر و تک کالبدی باشند. به عبارتی در صورتی که یک ماتریس ۸×۸ داشته باشیم، بایستی ۲۰۴ زیرماتریس آن را به لحاظ تک کالبدی بودن بررسی نماییم.
مزیت عمده این خاصیت این است که در برنامه ریزی تمام عدد صحیح، در صورتی که ماتریس ضرایب فنی دارای خاصیت کاملا تک‌کالبدی باشند، در اینصورت جواب‌های رهاشده خطی مساله عدد صحیح، همان جواب‌های مساله اصلی خواهند بود (تمامی متغیرها مقادیر صحیح می گیرند). به بیان دگر، پوسته محدب تمامی نقاط گوشه‌ای آن صحیح خواهند بود. برای بررسی کاملا تک‌کالبدی بودن یک برنامه‌ریزی عدد صحیح کافی است ماتریس ضرایب فنی آن را استخراج و تحلیل کرد.
اکثر علاقه مندان علم تحقیق در عملیات و بهینه سازی شاید برای یک بار هم که شده کتاب آقای ویلیامز (Williams) تحت عنوان مدل‌سازی در برنامه‌ریزی ریاضی (Model building in mathematical programming) را در طول دوره تحصیل‌شان مطالعه یا شنیده باشند. بدون شک یکی از منابع ارزشمند در زمینه دانش مدل‌سازی این مرحع هست. در بخش تجزیه (decomposition) این کتاب، آقای ویلیامز شرح می دهد:
الگوریتم های تجزیه از اهمیت محاسباتی قابل توجهی برخوردار هستند به این ترتیب که این الگوریتم ها امکان حل مسایل یکپارچه را در ابعاد وسیع میسر می سازند. علی رغم این مساله، روش های تجزیه با موفقیت های محاسباتی محدودی روبرو شده اند. الگوریتم دانتزیگ-ولف (Dantzig-Wolfe) محبوبیت بیشتری را در میان سایر الگوریتم های تجزیه بدست آورده است. علی رغم این محبوبیت اغلب اوقات حل مدل به صورت یکپارچه بسیار کاراتر از حل مدل توسط الگوریتم های تجزیه خواهد بود! مهمترین توصیه به شخصی که علاقه مند به تجزیه مساله مورد نظر خود و حل آن توسط یکی از روش های تجزیه می باشد اینه که این تصمیم حتما بایستی مبنای تجربی داشته باشد و صرفا جنبه تلاش-برای-حل-موثر نباشد.
بسیاری از علاقه‌مندان این روش‌ها از این موضوع شکایت دارند که ماه‌ها تلاش برای پیاده‌سازی روش‌های تجزیه همانند دانتزیگ ولف (dantzig wolf) یا بندرز (Benders) در نهایت منجر به بهبود اندکی در زمان حل و اجرای مدل شده‌اند.
پروفسور مارکو لوبکه (Marco Lübbecke) در پاسخ به این ابهام اذعان دارند که سرعت بخشی به این دسته الگوریتم‌ها دانش و مهارت‌های خاصی می‌طلبد. ایشان اشاره دارند که بسیاری از دانشجویان نسخه‌های ساده و پیش پا افتاده‌ای از این الگوریتم‌ها را بکار می‌گیرند که از عهده حل مثال‌هایی در مقیاس بزرگتر بر نخواهند آمد.
ایشان دو solver متن‌باز Dip و GCG را جهت شناسایی مشخصه‌های ساختاری مساله و پیاده‌سازی الگوریتم‌های تجزیه پیشنهاد کرده‌اند.
