İçeriğe atla
Arama sonuçlarına dön

Kısıt Programlama

Ortaya koyan
Rossi, van Beek & Walsh
Yıl
2006
Tür
Declarative combinatorial optimization
Aile
Mathematical programming

Bu metin makine çevirisidir ve henüz incelenmedi. Asıl metni İngilizce oku

Yazı boyutu

Ne işe yarar?

Kısıt Programlama (CP), bir problemin değişkenler, sonlu etki alanları ve kısıtlamalar kümesi olarak formüle edildiği ve bir çözücünün sistematik olarak tüm kısıtlamaları sağlayan atamaları aradığı beyana dayalı bir optimizasyon paradigmasıdır.

Rossi, van Beek ve Walsh tarafından 2006 tarihli Handbook of Constraint Programming adlı eserlerinde kapsamlı bir şekilde biçimlendirilen CP, çizelgeleme, planlama ve yapılandırma alanlarındaki birleştirici problemleri ele almak için yayılma tabanlı budamayı akıllı geri izleme aramasıyla birleştirir.

Yöntemin mantığı

CP'yi karmaşık bir bulmacayı doldurmak gibi düşünün: her hücre, bir dizi yasal değere sahip bir değişkendir ve bulmacanın her kuralı bir kısıtlamadır. CP, körlemesine tahmin etmek yerine, bir hücre doldurulduğunda komşu hücrelerden imkansız değerleri hemen ortadan kaldırmak için kuralları kullanır. Bu yayılma, arama alanını önemli ölçüde daraltır, böylece çözücü yalnızca makul kombinasyonları keşfeder - yalnızca bir çıkmaza ulaşıldığında geri izleme ve revize etme.

Tarih

Kısıt Programlama, 1970'lerde Montanari ve Mackworth'un kısıt tatmini üzerine erken çalışmalarıyla yapay zeka araştırmalarından doğmuştur. 1980'ler ve 1990'larda yay tutarlılığı algoritmaları, küresel kısıtlamalar ve CHIP ve ILOG Solver gibi pratik çözücülerin geliştirilmesiyle olgunlaşmıştır. Alan, 2006 tarihli Handbook of Constraint Programming'de Rossi, van Beek ve Walsh tarafından yetkili bir şekilde konsolide edilmiş ve teori, algoritmalar ve birleştirici optimizasyon uygulamalarını kapsayan kesin referans olmaya devam etmektedir.

Ne zaman kullanılır?

Kısıt Programlama, fizibilitenin optimallik kadar önemli olduğu çizelgeleme, zaman çizelgesi oluşturma, yapılandırma ve yönlendirme gibi karmaşık, heterojen kısıtlamalara sahip birleştirici problemler için en uygunudur. Ayrık veya sayılabilir değişken etki alanlarıyla modellenebilen problemler varsayar. CP, sürekli optimizasyon veya büyük ölçekli doğrusal programlar için daha az etkilidir; bu tür problemler için tipik olarak Doğrusal Programlama veya Karma-Tamsayı Programlama çözücüleri baskındır. Kısıtlamaların oldukça yapılandırıldığı ve yayılmanın arama alanının büyük bölümlerini budayabildiği durumlarda, CP genel amaçlı meta-sezgisellerden daha iyi performans gösterir.

Sınırlar ve dikkat edilmesi gerekenler

  • Ölçeklenebilirlik: en kötü durum üstel arama, CP'yi zayıf yayılmaya sahip çok büyük örneklerde yavaşlatır.
  • İyi modelleme gerektirir: kötü değişken/değer sıralama sezgiselleri veya eksik küresel kısıtlamalar gereksiz yere büyük arama ağaçlarına yol açar.
  • Sürekli etki alanları: CP, yerel olarak ayrık etki alanları için tasarlanmıştır; sürekli problemler özel uzantılar veya hibrit yaklaşımlar gerektirir.
  • Çözücü uzmanlığı: etkili kullanım, kısıt modelleme teknikleri ve çözücüye özgü küresel kısıt kitaplıkları hakkında bilgi gerektirir.

Kaynak metnin koşulları, bağımsız bilimsel inceleme veya analiz motoru doğrulaması yerine geçmez.

Güçlü yönleri

  • Beyana dayalı modelleme: karmaşık gerçek dünya kuralları, arama prosedürünü belirtmeden doğrudan kısıtlamalar olarak ifade edilir.
  • Güçlü budama: kısıt yayılması, fizibilitesi olmayan bölgeleri erken eler ve genellikle aramayı büyüklük mertebeleriyle azaltır.
  • Heterojen kısıtlamaları işler: mantıksal, aritmetik, küresel ve kullanıcı tanımlı kısıtlamalar tek bir modelde doğal olarak bir arada bulunur.
  • Tamlık garantisi: çözücü, sezgisel yöntemlerin aksine, ya optimal bir çözüm bulur ya da fizibiliteyi kanıtlar.

Uygulama alanları

  • Çalışan ve hemşire çizelgeleme: uygunluk, iş hukuku ve beceri kısıtlamalarını sağlarken personeli vardiyalara atama.
  • Zaman çizelgesi oluşturma: oda kapasitesi, eğitmen uygunluğu ve müfredat kısıtlamaları altında üniversite veya okul zaman çizelgeleri oluşturma.
  • Yapılandırma: uyumluluk ve kaynak kısıtlamaları altında bileşen kataloglarından ürün yapılandırmaları (bilgisayarlar, araçlar) birleştirme.
  • Araç yönlendirme ve lojistik: zaman pencereleri, araç kapasiteleri ve sürücü düzenlemeleri uyarınca teslimat rotaları planlama.
  • Birleştirici açık artırmalar ve kaynak tahsisi: münhasırlık ve bütçe kısıtlamaları altında kaynakları teklif verenlere veya görevlere atama.

Nasıl çalışır?

Nasıl çalışır?

1

Problem, değişkenler X, sonlu etki alanları D ve kısıtlamalar C kümesinden oluşan bir Kısıt Tatmin Problemi üçlüsü olarak kodlanır. Her değişken x_i, etki alanı D_i'den herhangi bir değer alabilir. Kısıtlamalar, değişken alt kümeleri arasındaki izin verilen değer kombinasyonlarını tanımlar ve gerçek dünya kurallarını - kapasite sınırları, öncelik ilişkileri, kaynak çakışmaları - çözücünün üzerinde akıl yürütebileceği matematiksel bir yapıya çevirir.

Formül
\text{CSP} = \langle X, D, C \rangle \quad X = \{x_1, x_2, \ldots, x_n\},\; D = \{D_1, D_2, \ldots, D_n\}
2

Arama öncesinde ve sırasında, çözücü herhangi bir geçerli çözümde yer alamayacak etki alanı değerlerini budamak için yay tutarlılığı ve diğer yerel tutarlılık algoritmalarını uygular. Kısıtlanmış değişkenlerin her çifti için, yay tutarlılığı, diğerindeki destekleyici bir değerin bulunmadığı bir değişkenin etki alanından değerleri kaldırır. Bu yayılma, her atamadan sonra tekrarlı olarak tetiklenir ve etkili arama alanını önemli ölçüde azaltır.

Formül
\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}
3

Çözücü, atanmamış bir değişkeni seçer - tipik olarak minimum kalan değerler veya derece gibi sezgisel yöntemler kullanarak - ve varsayımsal olarak budanmış etki alanından bir değer atar. Yayılma tekrar çalışır; bir çelişki tespit edilirse (boş bir etki alanı), çözücü en son seçim noktasına geri izleme yapar ve alternatif bir değer dener. Geri sıçrama ve kötü kayıt, başarısızlıklardan kurtarmayı daha da hızlandırabilir.

Formül
x_i \leftarrow a_i \in D_i,\quad \text{propagate},\quad \text{if fail: backtrack and reassign}
4

Tüm değişkenlere her kısıtlamayla tutarlı değerler atandığında, tam atama S*, bir çözüm oluşturur. Optimizasyon problemleri için, bir amaç fonksiyonu aramayı en iyi uygun çözüme yönlendirir ve dallanma ve sınırlama stratejileri, küresel optimum onaylanana veya bir zaman sınırı aşılana kadar daha iyi çözümler bulundukça sınırı aşamalı olarak sıkılaştırır.

Formül
S^* = \{(x_1, a_1^*), \ldots, (x_n, a_n^*)\} : \forall c \in C,\; c(a_1^*, \ldots, a_n^*) = \text{true}

Sık yapılan hatalar

  • Modeli aşırı kısıtlamak, fazlalık veya çelişkili kısıtlamalarla, çözücünün yanlışlıkla fizibilite eksikliğini bildirmesine neden olur.
  • Küresel kısıtlamaları (örneğin, alldifferent, cumulative) ihmal etmek, özel algoritmaların ücretsiz olarak sağladığı yayılma fırsatlarını kaçırır.
  • Arama sezgisellerini göz ardı etmek ve varsayılan değişken/değer sıralamasına güvenmek, patolojik sıralamalarda üstel zamanı boşa harcayabilir.
  • Kısıt tatminini optimizasyonla karıştırmak: bir amaç fonksiyonu ve sınır sıkılaştırma eklemeyi unutmak, en iyisi değil, yalnızca ilk uygun çözümü verir.

Sık sorulan sorular

Kısıt Programlama, Tamsayı Doğrusal Programlamadan nasıl farklıdır?

Her ikisi de birleştirici problemleri çözse de, ILP tüm kısıtlamaların ve hedeflerin doğrusal olmasını gerektirir, bu da verimli LP-gevşetme sınırlarına olanak tanır. CP böyle bir doğrusallık gereksinimi getirmez ve bunun yerine kısıt yayılmasına ve sistematik aramaya dayanır. CP, karmaşık mantıksal ve küresel kısıtlamaları daha doğal bir şekilde işlerken, ILP genellikle güçlü doğrusal yapıya ve büyük değişken sayılarına sahip problemler üzerinde daha iyi ölçeklenir.

Küresel kısıtlamalar nelerdir ve neden önemlidirler?

Küresel kısıtlamalar, keyfi sayıda değişken üzerinde üst düzey kısıtlamalardır - örneğin, alldifferent (tüm değişkenler farklı değerler alır) veya cumulative (herhangi bir zamandaki kaynak kullanımı kapasiteyi aşmaz). Önemlidirler çünkü çözücüler her biri için özel, oldukça verimli yayılma algoritmaları uygularlar ve aynı koşulu birçok ikili kısıtlamaya ayrıştırarak elde edilenden çok daha güçlü budama sağlarlar, bu da arama alanının büyük bir kısmının keşfedilmemiş kalmasına neden olur.

Kısıt Programlama, yalnızca uygun çözümler mi yoksa optimal çözümler mi bulabilir?

CP, fizibilite aramasını bir amaç fonksiyonuyla birleştirerek optimal çözümler bulabilir. Çözücü dallanma ve sınırlama kullanır: uygun bir çözüm bulunduğunda, sonraki herhangi bir çözümün kesinlikle daha iyi olmasını gerektiren bir kısıtlama ekler ve hiçbir iyileştirme mümkün olmayana kadar devam eder. Bu, optimalliği onaylar. Çalışma süresi sınırlıysa, şimdiye kadar bulunan en iyi çözüm bir yaklaşım olarak döndürülür.

İlgili yöntemler

Kaynaklar

  1. Rossi, F., van Beek, P., & Walsh, T. (Eds.). (2006). Handbook of Constraint Programming. Elsevier.

    ISBN: 978-0-444-52726-4
    Kopyalandı.