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

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

دلایلی که باعث می‌شوند این بی‌قاعده‌گی‌ها منجر به عدم توانایی مدل‌سازی از طریق برنامه‌ریزی عدد صحیح و ریاضی شوند عبارت‌اند از:

۱- محدودیت‌هایی که طبیعت آنها غیرخطی است.

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

۳- از هم‌گسستگی‌های Disjunction متنوع، که منجر می‌شود اطلاعات ضعیفی از مدل رها شده‌ی خطی حاصل شود.

متودولوژی CP معایبی نیز دارد که می‌توان به عدم استفاده از رهاسازی خطی و عدم محاسبه‌ی فاصله‌ی مساله‌ی اصلی و دوال متناظر اشاره کرد.

رویه‌های حل CP اغلب در سه مرحله عمل می‌نمایند:

انتشار محدودیت Constraint Propagation: در این مرحله هدف استخراج جواب شدنی مساله است. ممکن است مدل دارای متغیرهایی با مقادیر متفاوت باشد، لیکن رویه‌ی حل برخی از این مقادیر را جهت همگام‌سازی آنها با مساله حذف می‌کند. در CP، الگوریتم‌های هوشمندی ابداع شده‌اند تا این مقادیر را به طور کارا حذف کنند. این الگوریتم‌ها حالت کنونی رویه‌ی حل را منتشر کرده و مقادیر غیرعادی و ناسازگار را حذف می‌کنند. تجربه نشان داده است که سطح استنتاج Inference Level این هوشمندی نقش کلیدی در همگرایی CP بازی می‌کند. بایستی توجه شود که هوشمندی الگوریتم چندان قابل اتکا نیست و روش‌های ریاضی و جبری نیز نباید در رویه‌ی حل به کلی کنار گذاشته شوند.

پس‌رفت Backtracking: گاهی اوقات رویه‌ی حل دچار سردرگمی شده به این دلیل که مقادیری تخصیص داده شده به متغیرها غیر ممکن است (زیرا از محدودیت‌ها تخطی کرده است). متعاقبا رویه‌ی حل بایستی انتخاب‌های قبلی را بررسی و مقادیر دیگری را امتحان کند. این روش پس‌رفت نام دارد. لزومی ندارد که حتما الگوریتم به جوابی غیر ممکن رسیده و سپس پس‌رفت انجام دهد. برخی اوقات جهت یافتن جواب‌های بعدی و بهتر در زیرشاخه‌ی جاری این روش ممکن است اجرا شود.

بهبود جواب Solution Polishing: در این مرحله، رویه‌ی حل از میان مقادیر انتخاب شده برای متغیرها با استفاده از تکنیک‌های بهینه‌سازی دقیق، بهترین جواب را استخراج می‌کند.

مقایسه قابلیت‌های دو پارادایم برنامه‌ریزی ریاضی و برنامه‌ریزی محدودیت

قابلیتبرنامه‌ریزی ریاضیبرنامه‌ریزی محدودیت
رهاسازی خطیبلهخیر
اندازه‌گیری اختلاف (فاصله‌ی دوگان)بلهخیر
نوع بهینگی


سراسریسراسری
محدودیت‌های مدل‌سازیمسایل غیرخطی درجه دو
(و دارای ماتریس هشین نیمه مثبت)
و فضای حل مخروطی
(دارای فضای محدب)
مسایل دارای فضای گسسته
محدودیت‌های ویژهخیربله
محدودیت‌های منطقیبلهبله
منشا نظریجبر خطیتئوری گراف و هوش مصنوعی

 

فایل‌های برنامه‌ریزی محدودیت

این محتوا برای اعضا قابل مشاهده است. لطفا وارد شوید
0 Comments
Inline Feedbacks
View all comments