Kısıtlama optimizasyonu veya kısıtlı programlama (CP), sorunun rastgele kısıtlamalar açısından modellendiği çok büyük bir aday grubundan uygulanabilir çözümleri belirlemeye verilen addır. CP sorunları birçok bilim ve mühendislik disiplinde ortaya çıkar. ("Programlama" kelimesi bir zamanlar "bilgisayar" kelimesinin "işlem yapan kişi" anlamına gelmesine benzer şekilde, biraz yanlış bir addır. Burada "programlama", bir bilgisayar dilinde programlamadan ziyade bir planın düzenlenmesini ifade eder.)
CP, optimizasyon (en uygun çözüm bulma) yerine fizibiliteyi (uygun bir çözüm bulma) temel alır ve amaç işlevi yerine kısıtlamalara ve değişkenlere odaklanır. Aslında, bir CP sorununun nesnel işlevi bile olmayabilir. Amaç, probleme kısıtlamalar ekleyerek çok büyük bir olası çözüm kümesini daha yönetilebilir bir alt kümeye daraltmak olabilir.
Çalışanlar için zaman çizelgesi, CP için çok uygun bir sorundur.
Sorun, sürekli çalışan şirketler (fabrikalar gibi) çalışanları için haftalık zaman çizelgeleri oluşturmaları gerektiğinde ortaya çıkar. Bunu çok basit bir örnekle açıklayalım: Bir şirket günde üç tane 8 saatlik vardiya yürütüyor ve dört çalışanından üçünü her gün farklı vardiyalara atıyor, dördüncü günü de farklı vardiyalara atıyor. Böyle küçük bir durumda bile olası programların sayısı çok büyüktür: Her gün 4! = 4 * 3 * 2 * 1 = 24 olası çalışan ataması vardır, dolayısıyla olası haftalık program sayısı 2474'tür.
Genellikle uygun çözümlerin sayısını azaltan başka kısıtlamalar olur. Örneğin, her çalışanın haftada en az minimum sayıda gün çalışması. CP yöntemi, yeni kısıtlamalar eklediğinizde hangi çözümlerin uygulanabilir olduğunu takip eder. Bu da, gerçek dünyadaki büyük planlama problemlerini çözmek için güçlü bir araç haline gelir.
CP; özel bilim dergileri, konferanslar ve farklı çözüm tekniklerinden oluşan bir cephaneliğiyle tüm dünyada yaygın ve aktif bir topluluğa sahiptir. CP, planlama, planlama ve diğer pek çok alanda heterojen kısıtlamalarla başarıyla uygulanmıştır.
Araçlar
Google, CP sorunlarını çözmek için birkaç yol sunar:
- CP-SAT çözücü: SAT (memnuniyet) yöntemlerini kullanan bir kısıtlı programlama çözücü.
- Orijinal CP çözücü: Yönlendirme kitaplığında kullanılan kısıtlı programlama çözücüsü.
Probleminiz doğrusal bir hedef ve doğrusal kısıtlamalarla model edilebiliyorsa bir doğrusal programlama probleminiz var demektir ve MPSolver'ı değerlendirmeniz gerekir. (Bununla birlikte, rota sorunları doğrusal bir modelle temsil edilse bile genellikle en iyi araç yönlendirme kitaplığımız sayesinde çözülür.)
Örnekler
Sonraki bölümde, kısıt programlama için birincil VEYA-Araçları çözücü olan CP-SAT çözücüyü açıklanmaktadır. (SAT, memnuniyet anlamına gelir: Çözücü, SAT problemlerini CP yöntemlerinin yanı sıra SAT problemleri çözme tekniklerini de kullanır.)
Aşağıda, CP-SAT çözücü için uygun olan zaman çizelgesi problemlerine bazı örnekler verilmiştir:
İki klasik CP problemi, N kraliçeleri problemi ve kriptaritmetik bulmacalarıdır.