شمارش تمامی جواب های معمای n وزیر

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

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

صفر تا صد مدل سازی گروبی gurobi در پایتون python (بخش دوم)

 

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

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

صفر تا صد مدل سازی گروبی gurobi در پایتون python (بخش اول)

 

با کامنت‌هایی که از دوستان عزیز گرفتم متوجه شدم که بسیاری در مراحل اجرای کدهای گروبی gurobi تحت زبان برنامه‌نویسی پایتون python به مشکل بر می‌خورند. در این پست و پست بعدی صفر تا صد اجرای یک مساله زنجیره تامین ساده تک سطحی و در هر مرحله احتمال بروز برخی مشکلات را بررسی می‌کنیم.

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

بهینه سازی و فناوری پردازش گرافیکی GPU

 

توسعه دهندگان بسته‌های بهینه‌سازی در سال‌های اخیر فناوری پردازش موازی parallel computing به کمک کارت های گرافیکی نسل پیشرفته و قابلیت GPU computing را با حساسیت بالایی پیگیری می‌کنند. محدودیت‌های جدی در حل مسایل برنامه‌ریزی خطی linear programming، عدد صحیح integer programming و درجه دو quadratic programming با استفاده از پردازش GPU وجود دارد. شایان ذکر است که این امر تا این لحظه محقق نشده است. دلایل متعددی برای عدم تحقق این پدیده ‌می‌توان عنوان کرد. این محدودیت‌ها در این پست بحث و بررسی می‌شود.

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

شمارش تعداد جواب‌های مربع جادویی در CP Optimizer

 

 

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

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

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


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

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

مساله حداکثر برش MAXCUT: مقایسه رهاسازی نیمه معین Semi-definite programming با رهاسازی خطی


برنامه‌ریزی نیمه‌معین semi-definite programming یا به‌اختصار SDP کلاسی از بهینه‌سازی محدب convex optimization است که کاربرد آن در علم تحقیق در عملیات بسیار موفق بوده است. پوسته عدد صحیح مسائل برنامه‌ریزی عدد صحیح را می‌توان با دقت بالایی با برنامه‌ریزی نیمه معین تقریب زد. در این پست قصد داریم به مسئله حداکثر برش MAXCUT در تئوری گراف پرداخته و رهاسازی نیمه‌معین آن را با رهاسازی خطی مقایسه نماییم.

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

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

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

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

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

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

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