بهینه‌سازی محدودیت ، یا برنامه‌نویسی محدودیت (CP)، نامی است که برای شناسایی راه‌حل‌های امکان‌پذیر از میان مجموعه‌ای بسیار بزرگ از نامزدها، که در آن مشکل را می‌توان بر اساس محدودیت‌های دلخواه مدل‌سازی کرد، داده می‌شود. مشکلات CP در بسیاری از رشته های علمی و مهندسی به وجود می آید. (کلمه "برنامه نویسی" کمی اشتباه است، شبیه به معنای "رایانه" زمانی "کسی که محاسبه می کند". در اینجا "برنامه نویسی" به جای برنامه نویسی به زبان کامپیوتری به ترتیب یک طرح اشاره دارد.)
CP به جای بهینه‌سازی (یافتن راه‌حل بهینه) مبتنی بر امکان‌سنجی (پیدا کردن یک راه‌حل امکان‌پذیر) است و به جای تابع هدف، بر روی محدودیت‌ها و متغیرها تمرکز می‌کند. در واقع، یک مشکل CP ممکن است حتی یک تابع هدف نداشته باشد - هدف ممکن است محدود کردن مجموعه بسیار بزرگی از راه حل های ممکن برای یک زیر مجموعه قابل مدیریت تر با افزودن محدودیت هایی به مسئله باشد.
نمونه ای از مشکلی که برای CP مناسب است، زمان بندی کارمندان است. مشکل زمانی به وجود می آید که شرکت هایی که به طور مداوم فعالیت می کنند - مانند کارخانه ها - باید برنامه های هفتگی برای کارمندان خود ایجاد کنند. در اینجا یک مثال بسیار ساده آورده شده است: یک شرکت سه شیفت 8 ساعته در روز دارد و سه نفر از چهار کارمند خود را هر روز به شیفت های مختلف اختصاص می دهد، در حالی که به نفر چهارم روز مرخصی می دهد. حتی در چنین مورد کوچکی، تعداد برنامه های ممکن بسیار زیاد است: هر روز، 4! = 4 * 3 * 2 * 1 = 24 تکالیف احتمالی کارمند، بنابراین تعداد برنامه های هفتگی ممکن 24 7 است که بیش از 4.5 میلیارد است. معمولاً محدودیت‌های دیگری وجود خواهد داشت که تعداد راه‌حل‌های امکان‌پذیر را کاهش می‌دهد - برای مثال، اینکه هر کارمند حداقل حداقل تعداد روز در هفته کار کند. روش CP زمانی که محدودیت‌های جدید را اضافه می‌کنید، راه‌حل‌هایی که امکان‌پذیر باقی می‌مانند را پیگیری می‌کند، که آن را به ابزاری قدرتمند برای حل مشکلات زمان‌بندی بزرگ و در دنیای واقعی تبدیل می‌کند.
CP دارای یک جامعه گسترده و بسیار فعال در سراسر جهان با مجلات علمی اختصاصی، کنفرانس ها، و زرادخانه ای از تکنیک های حل مختلف است. CP با موفقیت در برنامه‌ریزی، زمان‌بندی و حوزه‌های متعدد دیگر با محدودیت‌های ناهمگن استفاده شده است.
ابزار
گوگل چند راه برای حل مشکلات CP ارائه می دهد:
- حل کننده CP-SAT : یک حل کننده برنامه نویسی محدودیت که از روش های SAT (رضایت پذیری) استفاده می کند.
- حل کننده اصلی CP : یک حل کننده برنامه نویسی محدودیت که در کتابخانه مسیریابی استفاده می شود.
اگر مشکل شما می تواند با یک هدف خطی و محدودیت های خطی مدل شود، پس شما یک مشکل برنامه نویسی خطی دارید و باید MPSolver را در نظر بگیرید. (با این حال، مشکلات مسیریابی معمولاً با کتابخانه مسیریابی وسیله نقلیه ما بهتر حل می شود، حتی اگر بتوان آنها را با یک مدل خطی نشان داد.)
مثال ها
بخش بعدی حل کننده CP-SAT، حل کننده اولیه OR-Tools برای برنامه نویسی محدودیت ها را توضیح می دهد. (SAT مخفف satisfiability است: حل کننده از تکنیک هایی برای حل مسائل SAT همراه با روش های CP استفاده می کند.)
در اینجا چند نمونه از مشکلات زمان بندی که برای حل کننده CP-SAT مناسب هستند آورده شده است:
دو مسئله کلاسیک CP عبارتند از مسئله N-queens و پازل های رمزی .