برنامهریزی محدودیت (Constraint Programming)
- معرفیشده توسط
- Rossi, van Beek & Walsh
- سال
- 2006
- نوع
- Declarative combinatorial optimization
- خانواده
- Mathematical programming
این متن ترجمه ماشینی است و هنوز بازبینی نشده است. متن اصلی را به انگلیسی بخوانید
چه کاری انجام میدهد؟
برنامهریزی محدودیت (CP) یک پارادایم بهینهسازی اعلانی است که در آن یک مسئله به صورت مجموعهای از متغیرها، دامنههای متناهی و محدودیتها فرموله میشود و یک حلکننده به طور سیستماتیک به دنبال تخصیصهایی میگردد که همه محدودیتها را برآورده کنند.
CP که به طور جامع توسط روسی، ون بیک و والش در کتاب راهنمای برنامهریزی محدودیت (2006) فرموله شده است، هرس مبتنی بر انتشار را با جستجوی پسگرد هوشمند ترکیب میکند تا مسائل ترکیبیاتی را در حوزههای زمانبندی، برنامهریزی و پیکربندی حل کند.
شهود پشت روش
برنامهریزی محدودیت را مانند حل یک پازل پیچیده در نظر بگیرید: هر خانه یک متغیر با مجموعهای از مقادیر مجاز است و هر قانون پازل یک محدودیت است. به جای حدس زدن کورکورانه، CP از قوانین برای حذف فوری مقادیر غیرممکن از خانههای همسایه، هر زمان که یک خانه پر میشود، استفاده میکند. این انتشار، فضای جستجو را به شدت کاهش میدهد، به طوری که حلکننده تنها ترکیبات معقول را بررسی میکند — و تنها زمانی که به بنبست میرسد، پسگرد کرده و بازنگری میکند.
تاریخ
برنامهریزی محدودیت از تحقیقات هوش مصنوعی در دهه 1970 با کارهای اولیه مونتاناری و مکورث در زمینه ارضای محدودیت پدید آمد. این روش در دهههای 1980 و 1990 با توسعه الگوریتمهای سازگاری قوسی، محدودیتهای سراسری و حلکنندههای عملی مانند CHIP و ILOG Solver به بلوغ رسید. این حوزه به طور معتبر توسط روسی، ون بیک و والش در کتاب راهنمای برنامهریزی محدودیت (2006) تثبیت شد، که همچنان مرجع قطعی است و تئوری، الگوریتمها و کاربردها را در بهینهسازی ترکیبیاتی پوشش میدهد.
چه زمانی استفاده شود
برنامهریزی محدودیت برای مسائل ترکیبیاتی با محدودیتهای پیچیده و ناهمگن — زمانبندی، برنامهریزی درسی، پیکربندی و مسیریابی — که در آنها امکانپذیری به اندازه بهینگی مهم است، مناسبتر است. این روش فرض میکند که مسائل را میتوان با دامنههای متغیر گسسته یا قابل شمارش مدلسازی کرد. CP برای بهینهسازی پیوسته یا برنامههای خطی در مقیاس بزرگ، که در آنها حلکنندههای برنامهریزی خطی یا برنامهریزی عدد صحیح مختلط معمولاً غالب هستند، کمتر مؤثر است. هنگامی که محدودیتها بسیار ساختاریافته هستند و انتشار میتواند بخشهای بزرگی از فضای جستجو را هرس کند، CP از فرااکتشافیهای عمومی بهتر عمل میکند.
محدودیتها و ملاحظات
- مقیاسپذیری: جستجوی نمایی در بدترین حالت، CP را در نمونههای بسیار بزرگ با انتشار ضعیف کند میکند.
- نیاز به مدلسازی خوب: اکتشافیهای ضعیف برای ترتیب متغیر/مقدار یا عدم وجود محدودیتهای سراسری منجر به درختان جستجوی بزرگ غیرضروری میشود.
- دامنههای پیوسته: CP به طور بومی برای دامنههای گسسته طراحی شده است؛ مسائل پیوسته نیاز به توسعههای تخصصی یا رویکردهای ترکیبی دارند.
- تخصص حلکننده: استفاده مؤثر مستلزم آشنایی با تکنیکهای مدلسازی محدودیت و کتابخانههای محدودیت سراسری خاص حلکننده است.
شرایط منبع جایگزین بررسی علمی مستقل یا اعتبارسنجی توسط موتور تحلیل نیست.
نقاط قوت
- مدلسازی اعلانی: قوانین پیچیده دنیای واقعی مستقیماً به عنوان محدودیتها بیان میشوند بدون اینکه رویه جستجو مشخص شود.
- هرس قدرتمند: انتشار محدودیت مناطق غیرممکن را زودتر حذف میکند و اغلب جستجو را به میزان قابل توجهی کاهش میدهد.
- مدیریت محدودیتهای ناهمگن: محدودیتهای منطقی، حسابی، سراسری و تعریفشده توسط کاربر به طور طبیعی در یک مدل واحد همزیستی دارند.
- تضمین کامل بودن: حلکننده یا یک راهحل بهینه پیدا میکند یا عدم امکانپذیری را اثبات میکند، برخلاف روشهای اکتشافی.
کاربردها
- زمانبندی کارکنان و پرستاران: تخصیص کارکنان به شیفتها با رعایت محدودیتهای در دسترس بودن، قانون کار و مهارت.
- برنامهریزی درسی: ساخت برنامههای درسی دانشگاهی یا مدرسهای با رعایت محدودیتهای ظرفیت اتاق، در دسترس بودن استاد و برنامه درسی.
- پیکربندی: مونتاژ پیکربندیهای محصول (رایانهها، وسایل نقلیه) از کاتالوگهای قطعات تحت محدودیتهای سازگاری و منابع.
- مسیریابی وسایل نقلیه و لجستیک: برنامهریزی مسیرهای تحویل با رعایت پنجرههای زمانی، ظرفیت وسایل نقلیه و مقررات راننده.
- مزایدههای ترکیبیاتی و تخصیص منابع: تخصیص منابع به پیشنهاددهندگان یا وظایف تحت محدودیتهای انحصاری و بودجه.
چگونه کار میکند
چگونه کار میکند
مسئله به صورت یک سهتایی مسئله ارضای محدودیت متشکل از متغیرهای X، دامنههای متناهی D و مجموعهای از محدودیتهای C کدگذاری میشود. هر متغیر x_i میتواند هر مقداری را از دامنه D_i خود بگیرد. محدودیتها ترکیبات مجاز مقادیر را در زیرمجموعههایی از متغیرها تعریف میکنند و قوانین دنیای واقعی — مانند محدودیتهای ظرفیت، روابط تقدم، تداخل منابع — را به یک ساختار ریاضی تبدیل میکنند که حلکننده میتواند بر روی آن استدلال کند.
فرمول
\text{CSP} = \langle X, D, C \rangle \quad X = \{x_1, x_2, \ldots, x_n\},\; D = \{D_1, D_2, \ldots, D_n\}قبل و در طول جستجو، حلکننده سازگاری قوسی و سایر الگوریتمهای سازگاری محلی را برای هرس کردن مقادیر دامنه که نمیتوانند در هیچ راهحل معتبری شرکت کنند، اعمال میکند. برای هر جفت متغیر محدود شده، سازگاری قوسی مقادیری را از دامنه یک متغیر حذف میکند که هیچ مقدار پشتیبانکنندهای در دامنه متغیر دیگر برای آنها وجود ندارد. این انتشار پس از هر تخصیص به طور مکرر فعال میشود و فضای جستجوی مؤثر را به شدت کاهش میدهد.
فرمول
\text{AC}(x_i, x_j): \forall a \in D_i,\; \exists b \in D_j \text{ s.t. } c_{ij}(a, b) \text{ holds}حلکننده یک متغیر تخصیصنیافته را انتخاب میکند — معمولاً با استفاده از اکتشافیهایی مانند حداقل مقادیر باقیمانده یا درجه — و به طور آزمایشی یک مقدار از دامنه هرسشده آن را به آن اختصاص میدهد. انتشار دوباره اجرا میشود؛ اگر تناقضی شناسایی شود (یک دامنه خالی)، حلکننده به آخرین نقطه انتخاب پسگرد میکند و یک مقدار جایگزین را امتحان میکند. پرش به عقب و ثبت موارد نامطلوب میتواند بازیابی از شکستها را بیشتر تسریع کند.
فرمول
x_i \leftarrow a_i \in D_i,\quad \text{propagate},\quad \text{if fail: backtrack and reassign}هنگامی که همه متغیرها با مقادیری سازگار با هر محدودیت تخصیص داده شدهاند، تخصیص کامل S* یک راهحل را تشکیل میدهد. برای مسائل بهینهسازی، یک تابع هدف جستجو را به سمت بهترین راهحل ممکن هدایت میکند و استراتژیهای شاخه و کران، کران را به تدریج با یافتن راهحلهای بهتر، تا زمانی که بهینگی سراسری تأیید شود یا محدودیت زمانی فرا رسد، سختتر میکنند.
فرمول
S^* = \{(x_1, a_1^*), \ldots, (x_n, a_n^*)\} : \forall c \in C,\; c(a_1^*, \ldots, a_n^*) = \text{true}دامهای رایج
- محدود کردن بیش از حد مدل با محدودیتهای زائد یا متناقض باعث میشود حلکننده به اشتباه عدم امکانپذیری را گزارش کند.
- نادیده گرفتن محدودیتهای سراسری (مانند alldifferent، cumulative) فرصتهای انتشار را که الگوریتمهای تخصصی به رایگان ارائه میدهند، از دست میدهد.
- نادیده گرفتن اکتشافیهای جستجو و تکیه بر ترتیب پیشفرض متغیر/مقدار میتواند زمان نمایی را در ترتیبهای پاتولوژیک هدر دهد.
- اشتباه گرفتن ارضای محدودیت با بهینهسازی: فراموش کردن اضافه کردن یک تابع هدف و سختتر کردن کران تنها اولین راهحل ممکن را به دست میدهد، نه بهترین راهحل را.
پرسشهای متداول
برنامهریزی محدودیت چه تفاوتی با برنامهریزی خطی عدد صحیح دارد؟
در حالی که هر دو مسائل ترکیبیاتی را حل میکنند، برنامهریزی خطی عدد صحیح (ILP) مستلزم آن است که همه محدودیتها و اهداف خطی باشند، که امکان کرانهای کارآمد آرامسازی برنامهریزی خطی را فراهم میکند. CP چنین الزامی برای خطی بودن ندارد و در عوض بر انتشار محدودیت و جستجوی سیستماتیک تکیه میکند. CP محدودیتهای منطقی و سراسری پیچیده را به طور طبیعیتر مدیریت میکند، در حالی که ILP اغلب در مسائلی با ساختار خطی قوی و تعداد زیاد متغیرها بهتر عمل میکند.
محدودیتهای سراسری چه هستند و چرا اهمیت دارند؟
محدودیتهای سراسری، محدودیتهای سطح بالا بر روی تعداد دلخواهی از متغیرها هستند — به عنوان مثال، alldifferent (همه متغیرها مقادیر متمایز میگیرند) یا cumulative (استفاده از منابع در هر زمان از ظرفیت تجاوز نمیکند). آنها اهمیت دارند زیرا حلکنندهها الگوریتمهای انتشار اختصاصی و بسیار کارآمدی را برای هر یک پیادهسازی میکنند که هرس بسیار قویتری را نسبت به تجزیه همان شرط به بسیاری از محدودیتهای دوتایی به دست میآورند، که بخش زیادی از فضای جستجو را کشفنشده باقی میگذارد.
آیا برنامهریزی محدودیت میتواند راهحلهای بهینه را پیدا کند یا فقط راهحلهای ممکن را؟
CP میتواند با ترکیب جستجوی امکانپذیری با یک تابع هدف، راهحلهای بهینه را پیدا کند. حلکننده از شاخه و کران استفاده میکند: هنگامی که یک راهحل ممکن یافت میشود، یک محدودیت اضافه میکند که هر راهحل بعدی باید به طور قطعی بهتر باشد، و این روند را تا زمانی که هیچ بهبودی ممکن نباشد ادامه میدهد. این کار بهینگی را تأیید میکند. اگر زمان اجرا محدود باشد، بهترین راهحل یافت شده تا کنون به عنوان یک تقریب بازگردانده میشود.
روشهای مرتبط
منابع
Rossi, F., van Beek, P., & Walsh, T. (Eds.). (2006). Handbook of Constraint Programming. Elsevier.
شابک: 978-0-444-52726-4کپی شد.