CP-SAT ve Python ile Kısıt Programlamaya Pratik Giriş

Kısıt programlamaya pratik bir giriş: CP-SAT ve Python

Bildirimsel paradigma

• Kısıt programlama (CP), ayrık optimizasyon problemlerini çözmek için kullanılan bildirimsel bir paradigmadır
• Emirsel programlamadan farklı olarak, istenen sonuç tanımlanır ve program sonucu kendi başına çıkarır
• Örneğin, yetişkinler listesini çıkarma durumunda emirsel yaklaşım ile bildirimsel yaklaşım arasındaki fark açıklanır

Kısıt programlamanın (CP) temelleri

• Model: problemin istenen sonucunu tanımlamak
• Değişkenler: bulunmak istenen değerler; her değişkenin bir alanı (izin verilen değerler kümesi) vardır
• Kısıtlar: değişkenler arasındaki ilişkileri tanımlar
• Çözüm: değişkenlere değer atayarak kısıtları karşılamak

Python ve CP-SAT ile pratik bir örnek

• Problem: çalışanlar için haftalık çalışma çizelgesi oluşturmak
• Model oluşturma: CP-SAT kullanılarak boş bir model oluşturulur
• Veriler: çalışan listesi ve rolleri, çalışma günleri, vardiya saatleri tanımlanır
• Değişken tanımlama: her çalışanın çalışıp çalışmadığını gösteren Boolean değişkenler oluşturulur
• Kısıt ekleme: problem tanımına göre değişkenlere kısıtlar eklenir

Modelin çözülmesi

• Çözme: model çözülür ve sonuç elde edilir
• Ek kısıtlar: fazla mesainin önlenmesi, belirli çalışanların çalışma süresinin sınırlandırılması, belirli çalışanlar arasında çalışma saatlerinin çakışmasının önlenmesi gibi ek kısıtlar eklenir

Ara bölüm: çözüm durumu

• Çözüm durumu: optimal, uygulanabilir, uygulanamaz, bilinmiyor gibi durumlar döndürülür
• Örnek: basit bir örnek üzerinden her durum açıklanır

"Üzgünüm, Emma"

• Uygulanamaz durum: Emma'nın hafta içi 5 gün izinli olması mümkün değildir
• Alternatif öneri: Emma'nın hafta içi yalnızca 3 gün izinli olması önerilir

Hedef: çalışma saatlerinin eşit dağıtılması

• Hedef ekleme: çalışma saatlerini eşit dağıtmak için bir hedef eklenir
• Sonuç: her çalışanın çalışma saatleri dengeli şekilde dağıtılır

Sonuç

• Temel kavramlara giriş: kısıt programlamanın temel kavramları tanıtılır ve pratik bir örnekle açıklanır
• Sonraki yazıya ön bakış: sonraki yazıda Postgres'in indeks seçiminde kısıt programlamanın nasıl kullanılacağı ele alınacaktır

GN⁺ görüşü

• Kısıt programlamanın faydası: karmaşık optimizasyon problemlerini çözmede son derece faydalıdır
• CP-SAT'ın güçlü yönü: Google'ın OR-Tools projesinin bir parçası olarak geliştirilen CP-SAT güçlü performans sunar
• Gerçek dünyada uygulama örneği: çalışan vardiya planlaması gibi gerçek problemlere uygulanabilir
• Teknoloji benimsemede dikkat edilmesi gerekenler: yeni bir teknolojiyi benimserken öğrenme eğrisi ve mevcut sistemlerle entegrasyon sorunları dikkate alınmalıdır
• Benzer proje önerileri: IBM'in CPLEX'i, Gurobi gibi ticari çözücüler de benzer işlevler sunar

[GN⁺]

Hacker News yorumu

• Geçmişte kısıt çözücüleri kullanma deneyimim oldu ve bu araçlar gerçekten şaşırtıcı performans gösteriyor

  • Sorun, yeni başlayanlara yönelik neredeyse hiç kaynak olmaması
  • Kaynakların çoğu ya Sudoku çözmeyi anlatıyor ya da son derece teknik araştırma materyallerinden oluşuyor
  • Daha fazla problemi çözebilen araçların daha erişilebilir olmasını isterdim
  • Erişilebilir olması, yine de bir programcı gerektirdiği anlamına geliyor

• Eski kitabımdaki MiniZinc ve Python kullanan kısa bir bölümü yeniden yazıyorum

  • MiniZinc bir kısıt programlama sistemi
  • Coursera'da MiniZinc kullanan iyi bir ders var

• Birçok program tek bir veri gösterimine sahip olmaya çalışıyor, ama bu çoğu durumda mantıklı değil

  • Algoritmaların yeni bir gösterimle çalışmasını sağlamak için çok fazla çarpıtma gerekiyor
  • Gösterimleri daha sık dönüştürmememiz hep bana üzücü gelmiştir
  • Gösterimi dönüştürdüğünüzde çok daha özlü bir ifade elde edebilirsiniz ve bu da daha hızlı çalışmayı mümkün kılar

• Spor kampı işleten bir müşterim var

  • Çocuklar istedikleri sporları ve arkadaşlarını talep edebiliyor
  • Bu, insanlar için zor bir çizelgeleme problemi yaratıyor
  • OR-Tools tabanlı bir optimizasyon aracı kullanarak basit bir sistem kurdum
  • Artık çizelge birkaç tıklamayla tamamlanıyor

• 2000'lerin başında birçok çözücü kullanma deneyimim oldu

  • Şu anda Python kullanan yazılım (web) işleri yapıyorum
  • Bu konunun derinlemesine ele alındığını görmek sevindirici
  • Kısıtları bir modele dönüştürmek işin %90'ı ve en zor kısmı

• Ağırlıklı olarak kısıt çözücü olarak çalışan parametrik bir CAD olup olmadığını merak ediyorum

  • Başlangıçta umursamadığınız parametre değerlerini tahmin etmek zorunda kalmak sık sık can sıkıcı oluyor
  • Bunun yerine ilgilendiğim parametreleri kısıtlayıp geri kalanını optimize etmek isterdim

• Karma tamsayılı programlamayla karşılaştırınca nasıl olurdu, merak ediyorum