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

 (pganalyze.com)
1 puan yazan GN⁺ 2024-07-05 | 1 yorum | WhatsApp'ta paylaş
  • Kısıt programlama (CP), ayrık optimizasyon problemlerini prosedürel kodla değil değişkenler, alanlar ve kısıtlarla modelleyip, çözücünün koşulları sağlayan bir çözüm bulmasını sağlayan deklaratif bir yaklaşımdır
  • Modelin özü, bulunacak değerleri temsil eden değişkenler, olası değer aralığı olan alanlar ve değişkenler arasındaki ilişkileri sınırlayan kısıtlardır; gerekirse daha iyi bir çözüm seçmek için bir amaç fonksiyonu kullanılabilir
  • Alice, Bob ve Carol’ın şeker parasını paylaşma örneği, alldifferent, maximum, minimize ile geçerli bir çözümü daha dengeli bir çözüme iyileştirme akışını gösterir
  • Pratik örnek, Google OR-Tools’un açık kaynak çözücüsü CP-SAT ve Python ile 4 çalışanın 7 gün, 3 vardiya, 2 rolden oluşan haftalık çalışma çizelgesini oluşturur
  • Aynı modele haftalık 40 saat üst sınırı, ders programı, birlikte çalışmaması gereken kombinasyonlar, hafta sonu çalışmasının dengeli dağıtımı, izin talepleri ve çalışma sayısı farkını en aza indirme gibi koşullar aşamalı olarak eklenebilir

Kısıt programlamanın temel düşünme biçimi

  • Kısıt programlama (CP), ayrık optimizasyon problemlerini çözmeye yönelik deklaratif bir paradigmadır
  • Emir kipindeki programlama, sonuca ulaşan adımları sırayla yazar; deklaratif yaklaşım ise istenen sonucun koşullarını tanımlar ve yürütme sisteminin o sonucu bulmasını sağlar
  • Yetişkinlerin listesini çıkarma örneğinde emir kipindeki kod kişi listesini dolaşıp Age >= 18 kontrolü yaparken, deklaratif SQL koşulu SELECT person_name FROM people WHERE age >= 18; gibi doğrudan ifade eder
  • CP de istenen sonucu bir model olarak tanımlar; temel bileşenler değişkenler, alanlar ve kısıtlardır
    • Değişkenler neyin bulunacağını gösterir
    • Alan, bir değişkenin alabileceği değerler kümesidir
    • Kısıtlar, değişkenler arasındaki ilişkileri sınırlar

Değişkenler, alanlar, kısıtlar ve amaç fonksiyonu

  • Çözüm, her değişkenin kendi alanı içindeki bir değeri aldığı ve tüm kısıtları karşıladığı atamadır
  • Şeker parası örneği, Alice, Bob ve Carol’ın her birinin en fazla 20 doları olduğu ve 50 dolarlık şeker almak için para topladığı bir problemdir
    • a, b, c değişkenleri her kişinin ödediği tutardır
    • Üç değişkenin alanı {0, ..., 20}’dir
    • a + b + c == 50 ile toplam tutar sağlanır
    • a >= b ile Alice’in Bob’dan en az aynı miktarı ödemesi sağlanır
    • c % 5 == 0 ile Carol’ın tutarı 5’in katlarıyla sınırlandırılır
    • Üç kişinin aynı tutarı ödememesi için a != b, a != c, b != c konulabilir
  • Birden çok değişkeni kapsayan koşullar global kısıtlar (global constraints) olarak ifade edilebilir; alldifferent(a, b, c) üç değişkenin de farklı değerler almasını sağlar
  • Çözücü modeli girdi olarak alır ve geçerli bir çözüm döndürür
    • Örnek çözüm a = 19, b = 11, c = 20 tüm kısıtları karşılar
    • Ancak Carol, Bob’un neredeyse iki katını ödediği için daha dengeli bir çözüm olabilir
  • Amaç fonksiyonu, kısıtları sağlayan çözümler arasından belirli bir ifadeyi en aza indirir veya en çoğa çıkarır
    • Yeni değişken x en büyük katkı payı olarak belirlenir ve maximum(x, [a, b, c]) kullanılır
    • minimize: x uygulandığında a = 18, b = 17, c = 15, x = 18 döndürülür
    • En büyük katkı payı ile en küçük katkı payı arasındaki fark 9 dolardan 3 dolara düşer

CP-SAT ve Python ile vardiya çizelgesi modeli oluşturma

  • Pratik örnek, küçük bir mağazanın haftalık çalışma çizelgesini oluşturma problemidir
    • Mağaza her gün 08.00’den 20.00’ye kadar açıktır
    • Bir gün Morning, Afternoon, Evening olmak üzere üç vardiyadan oluşur ve her vardiya 4 saattir
    • Roller Cashier ve Restocker olmak üzere iki tanedir
    • Çalışanlar Phil, Emma, David ve Rebecca adlı dört kişidir
  • CP-SAT, Google OR-Tools içinde yer alan açık kaynak bir CP çözücüsüdür
  • Boş bir model, ortools.sat.python içindeki cp_model.CpModel() ile oluşturulur
  • Çalışanlara göre yapabilecekleri roller şöyledir
    • Phil: Restocker
    • Emma: Cashier, Restocker
    • David: Cashier, Restocker
    • Rebecca: Cashier
  • Çalışma çizelgesi, çalışan, rol, gün ve vardiya kombinasyonundan oluşan Boole değişkenleriyle ifade edilir
    • schedule["Emma"]["Restocker"]["Monday"]["Evening"], Emma pazartesi akşam vardiyasında Restocker olarak çalışıyorsa 1, çalışmıyorsa 0 olur
    • model.new_bool_var(), alanı {0, 1} olan bir değişken oluşturur

Temel çalışma kısıtları

  • Tüm zaman dilimlerinde tam olarak bir kasiyer gerektiği için, her gün ve vardiya için Cashier rolünün toplamı 1 olmalıdır
  • Stok görevlisi günde yalnızca bir vardiyada gerektiğinden, her günün Restocker rolü toplamı 1 olarak belirlenir
  • Önceki günün Evening stok vardiyası ile ertesi günün Morning stok vardiyasının art arda gelmemesi için iki atamanın toplamı 1’i aşmayacak şekilde sınırlandırılır
  • Bir çalışan aynı vardiyada aynı anda iki rol üstlenemeyeceğinden, çalışan, gün ve vardiya bazındaki rol toplamı 1 veya daha az olmalıdır
  • Yetkisi olmayan rol atanmaması için ilgili çalışanın yapamayacağı rollere ait değişkenlerin tümü 0 olarak sabitlenir
  • Bir günde en fazla çalışma süresi 8 saat, yani 2 vardiyadır
    • Aynı gün hem Morning hem Evening atanırsa Afternoon boyunca 4 saatlik boşta kalma süresi oluşur
    • Çalışan ve gün bazında Morning ile Evening atamalarının toplamı 1 veya daha azla sınırlandırılarak hem günde 2 vardiyadan fazla çalışma hem de aradaki boş süre engellenir

Çözücüyü çalıştırma ve ilk sonuçlar

  • Modeli çözmek için cp_model.CpSolver() oluşturulur ve solver.solve(model) çağrılır
  • Çözüm elde edildikten sonra solver.value(...) ile schedule değişkenlerinin değerleri okunur
  • İlk çalışma çizelgesi tüm temel kısıtları karşılasa da Rebecca’nın bir haftada 14 vardiya üstlendiği bir sonuç ortaya çıkar
  • Fazla mesaiyi önlemek için her çalışanın haftalık çalışmasını en fazla 40 saat, yani 10 vardiya ile sınırlayan bir kısıt eklenir
  • Phil tam zamanlı bir öğrenci olduğu için haftada tam olarak 4 vardiya çalışır ve hafta içi Morning ile Afternoon vardiyalarında dersleri nedeniyle çalışamaz
  • Phil ile Emma’nın aynı vardiyada çalışmaması için her gün ve vardiyada iki kişinin atamalarının toplamı 1 veya daha azla sınırlandırılır
  • Herkesin sevmediği hafta sonu çalışması, cumartesi ve pazar günlerindeki toplam 8 vardiyanın dört çalışana 2’şer vardiya olacak şekilde dağıtılmasıyla kısıtlanır

Çözüm durumu: OPTIMAL, INFEASIBLE, FEASIBLE, UNKNOWN

  • Çözücü modeli girdi olarak alır ve bir durum ile çözüm döndürür
  • OPTIMAL, daha iyi bir çözümün bulunmadığı bir çözümün bulunduğu anlamına gelir
    • Örneğin x + y >= 5 olup x + y en aza indirildiğinde (x, y) = (5, 0) optimal çözümdür
    • (x, y) = (3, 2) de aynı amaç değerine sahip olduğundan optimal çözüm olabilir
  • INFEASIBLE, değişkenlere nasıl değer atanırsa atansın kısıtların karşılanamayacağı anlamına gelir
    • Örneğin x ∈ {0, ..., 10} iken x >= 15 istenirse bu imkânsızdır
  • Büyük problemler veya karmaşık amaç fonksiyonları nedeniyle çözücü zaman sınırıyla durdurulursa iki durum ortaya çıkabilir
    • FEASIBLE: Kısıtları karşılayan bir çözüm bulunmuştur, ancak optimal olup olmadığı bilinmez
    • UNKNOWN: Çözüm bulunamamıştır; bir çözümün var olup olmadığı da bilinmez

İzin talebi ve adil dağıtım

  • Emma’nın pazartesiden cumaya kadar izinli olmak istediği kısıtı eklenirse çözücü durumu INFEASIBLE olur
    • Çünkü diğer kısıtları ihlal etmeden çalışma çizelgesi doldurulamaz
  • Emma’nın yalnızca pazartesiden çarşambaya kadar izinli olması koşuluna değiştirilirse çalışma çizelgesi oluşturulabilir
    • Phil istendiği gibi tam olarak 4 vardiya çalışır
    • Emma 6 vardiya, David 10 vardiya, Rebecca 8 vardiya üstlenir
  • Emma, David ve Rebecca arasındaki vardiya sayısını daha dengeli hâle getirmek için amaç fonksiyonu eklenir
    • Her çalışanın toplam vardiya sayısını gösteren total_shifts adlı tamsayı değişkenleri oluşturulur
    • model.new_int_var(0, 10, ...) ile 0’dan 10’a kadar değer alabilen tamsayı değişkeni oluşturulur
    • Phil yarı zamanlı olduğundan hariç tutulur ve model.add_min_equality(...) ile model.add_max_equality(...) kullanılarak en az ve en çok vardiya sayısı izlenir
    • model.minimize(max_shifts - min_shifts) ile en çok ve en az vardiya sayısı arasındaki fark en aza indirilir
  • Nihai sonuç Phil 4 vardiya, Emma 6 vardiya, David 9 vardiya, Rebecca 9 vardiyadır
    • Emma 3 gün izinli olduğu için 6 vardiya çalışır
    • David ve Rebecca aynı şekilde 9’ar vardiya olarak dağıtılır

Örnek kod ve sonraki konu

  • Bu model, mağaza sahibinin ve çalışanların gereksinimlerini aynı anda karşılayan bir çalışma çizelgesi oluşturur
  • Aynı CP modeline kısıtlar eklemeye devam ederek taleplerin mümkün olup olmadığı kontrol edilebilir ve mümkün çözümler arasından amaç fonksiyonuyla daha adil bir dağıtım bulunabilir
  • Örnek kod pganalyze GitHub üzerinde yayımlanmıştır
  • Sonraki yazının konusu, Postgres’te indeks seçimi için kısıt programlamanın nasıl kullanılacağıdır

İlgili okumalar

1 yorum

 
GN⁺ 2024-07-05
Hacker News yorumları

  • Daha önce bir kısıt çözücüsü kullanmıştım ve yapabildikleri gerçekten sihir gibi gelmişti. Sorun şu ki yeni başlayanların bakabileceği çok fazla kaynak yok
    Kaynakların çoğu ya Sudoku çözmekten ibaret (bu alanın Hello World’ü) ya da yalnızca alan uzmanlarına yönelik, son derece teknik birincil araştırma literatürü
    Üzücü olan şu: bu tür araçlar daha erişilebilir olsaydı muhtemelen inanılmaz derecede çok sayıda problemi çözebilirdik. Burada erişilebilir derken yine de bir programcı gerektiğini kastediyorum; ayrıca problemi bir kısıt DSL’ine dökmek çoğu insanın iyi yapabildiği bir şey değil

    • Bence bu araçların yeterince erişilebilir olmamasının nedeni, çözücülerin çoğunun karma tamsayılı programlama (MIP) tabanlı olması ve alanı matematiksel denklemlerle ifade etmenizi gerektirmesi. Bunun için kullanıcının hem alanı hem de matematiği bilmesi gerekiyor ki kısıtları doğru yazabilsin
      Ama çözücü dünyası yalnızca MIP’ten ibaret değil. Yerel arama tabanlı kısıt çözücüleri de var ve bu yaklaşımda tüm kısıtları tamsayı değişkenleri arasındaki ilişkiler ya da denklemler olarak modellemek zorunda değilsiniz
      Yerel arama çözücülerinde kısıtlar genellikle belirli bir çözümün ne kadar iyi olduğunu söyleyen kara kutular olarak ele alınır. Bu yüzden tüm olası çözümleri denemediğiniz sürece en iyi çözümü garanti etmek zordur; ama makul süre içinde en iyiye yakın çözümler bulmakta iyidirler
      Timefold Solver bu tür yerel arama tabanlı çözücülerden biri. Kullanıcı, çözücünün değişkenleri ve olası değerleri anlayabilmesi için alana açıklamalar ekliyor. Böylece kısıtlar int yerine Shift ve Employee ile çalışıyor ve onların metotlarına da erişebiliyor
      Açıklama: Timefold Solver’da çalışıyorum
    • Aynen öyle. Kısıt çözücülerinin gerçek sözdizimini ya da API’sini öğrenmek çok kolay; bunlar fazla basit. Asıl zaman ve uzmanlık gerektiren kısım, problemi modellemek ve buna benzer gerçek ölçekte ve karmaşıklıkta örneklerin neredeyse hiç olmaması
      Yaklaşık 5 yıldır MiniZinc ile çizelgeleme problemleri çözüyorum ama ne yazık ki o kodların hepsi kapalı kaynak, dolayısıyla açık kaynak olarak paylaşılmaları söz konusu değil
      Konteynerleştirme, görselleştirme ve modellemeyi de içeren uçtan uca bir kısıt programlama örneği yapmak isterdim; ama gerçekten çözmeye değer ve kullanılabilecek açık kaynak verisi olan bir problem bulmak başlı başına bir engel
    • Teorinin kendisinden çok indirgeme (reduction) kısmının daha zor olduğuna katılıyorum. Dennis Yurichev’in "SAT/SMT by Example" (https://smt.st/) bu konuda iyi bir kaynak ama oldukça göz korkutucu
    • “Kaynakların çoğu ya Sudoku çözmekten ibaret ya da alan uzmanlarına yönelik araştırma literatürü” sözü çok doğru. Bir kural motorunda SAT çözücüsü kullanmayı denemiştim ama nasıl kullanmam gerektiğine dair hiçbir fikrim yoktu
      Epey çıkarım yaptıktan sonra temel bir kavram kanıtı oluşturabildim ama onu gerçekten ihtiyaç duyulan seviyeye ölçekleyemedim. Oyuncak bir uygulama ile daha pratik bir şey arasındaki fark çok büyüktü
    • Uzun yıllar kod yazdım ama şu sıralar biraz paslanmış durumdayım. Geçen yıl Google’ın OR-Tools aracıyla bir futbol takımı optimize edici yaptım; içinde arkadaşlarla aynı takımda olma gibi seçim kısıtları ve takımlar arasında beceri dengesini sağlama gibi koşullar vardı
      LLM’ler beni genel olarak doğru yöne oldukça hızlı götürmekte yardımcı oldu. Şu anda tam isabet sağlayamıyorlar ama sonrasında geri kalanını kendim tamamlayabileceğim kadar yardım ettiler

  • Bütün işin özü, bir şeyi çözücüye gönderilebilecek şekilde nasıl modelleyeceğinizi öğrenmekte yatıyor. Sonraki adım da ortaya çıkan çözümü insanların anlayabileceği biçimde ifade etmek
    Üzücü olan, çoğu programın veriyi tek bir gösterim biçiminde tutmaya çalışması ve bunun bu düşünce tarzına ters düşmesi. Çoğu durumda bu pek mantıklı değil ve algoritmaları yeni gösterime uydurmak için bir sürü dolambaç ortaya çıkıyor
    Bu yazı da başlarda deklaratif yaklaşıma kısaca değinerek bu konuya temas ediyor. Kodumun gösterimler arasında daha sık dönüşüm yapmıyor olmasına hep hayıflanırım. Böyle yapınca çok daha öz bir ifade elde ediyorsunuz ve bu sadelik sayesinde iki kat kazanç olarak hız da gelebiliyor
    Elbette bunun sonuçta pek çok veri hattını tarif eden bir söz olduğunun farkındayım. Yapının büyük kısmı veriyi dönüştürmeye ve onu farklı hesaplama noktalarına yönlendirmeye harcanıyor

  • Daha önce yazdığım ve şu anda yeniden yazmakta olduğum bir kitapta, Python’dan MiniZinc kullanımıyla ilgili kısa bir bölüm var: https://leanpub.com/pythonai/read#constraint-programming-wit...
    MiniZinc bir kısıt programlama sistemi. MiniZinc kullanımıyla ilgili iyi bir Coursera dersi de var

    • Coursera dersinin bağlantısı olup olmadığını merak ediyorum

  • Ekonometri okuduktan sonra 2000’lerin başında yöneylem araştırması yüksek lisansında çözücüleri çok kullandım. Şimdi Python kullanan web yazılımı tarafında çalışıyorum; bu konuda derinlikli bir yazı görmek hoşuma gitti
    Bu konuyu seviyorum ve yazıyı okuyunca birçok anı canlandı. Kısıtları bir modele (değişkenler, yapı vb.) dönüştürmenin işin %90’ı olduğunu ve en zor kısmı oluşturduğunu yeniden hissettim

    • Yüksek lisansta GAMS adlı bir program kullanmıştım
      Sözdizimi yapısı tamamen serbest biçimli
      https://www.gams.com/latest/docs/UG_GAMSPrograms.html#UG_GAM...
    • Kısıtları modele dönüştürmede LLM’ler oldukça yardımcı olabilir. LLM’den kısıt modeline çeviren bir adaptörü denemek istemiştim
      Kolay toplanabilecek bir meyve gibi görünüyor ama başkalarının da bundan fayda görüp görmeyeceğini merak ediyorum
    • Bence en zor kısım, bunu üretim ortamında sorunları en aza indirerek çalıştırmak. Ölçeklemek ve veri değişimlerine dayanıklı hâle getirmek çok zaman alıyor

  • Çocuklar için spor kampı işleten bir müşteri var. Çocuklar yapmak istedikleri sporları ve aynı grupta olmak istedikleri arkadaşlarını talep edebiliyor
    Bu yüzden insanların çözmesinin zor olduğu bir zamanlama problemi ortaya çıkmış ve eskiden her yıl birkaç haftalık iş gücü bu işe gidiyormuş. Müşterinin verilerini OR-Tools tabanlı bir optimizere bağlayan basit bir sistem yaptık; artık zamanlama birkaç tıklamayla tamamlanıyor

    • Aynen öyle. Verileri, kısıtları ve fayda fonksiyonunu sisteme düzgünce girerseniz yeterince iyi çözümleri çok hızlı biçimde bolca bulabilirsiniz
      Bir basketbol ligi koçluğu yapıyorum ve 8 periyot var. Hiçbir oyuncu başka bir oyuncudan 2 periyottan fazla oynayamaz. Maç başına mümkün olan kadro dizilişi sayısı, oynama süresi kısıtlarını sağlarken bile astronomik düzeyde fazla
      Kısıtları sağlayan kadro kümelerini bulmak çok kolay, ama en iyi ya da en iyiye yakın kadro kümelerini bulmak çok zor. Bir de geç gelen veya haber vermeden gelmeyen oyuncuları hesaba katmanız gerekiyorsa iş daha da ilginçleşiyor
      *Her zaman tamamen mümkün olmuyor
    • Bunu nasıl yaptığınızı ayrıntılı biçimde anlattığınız bir blog yazısı kesinlikle müthiş ilgi görürdü

  • Esas olarak bir kısıt çözücü gibi çalışan parametrik CAD olup olmadığını merak ediyorum
    Başta önemsemediğim parametre değerlerini kabaca tahmin etmek zorunda kalmak çok sık canımı sıkıyor. İlgilendiğim parametreleri kısıt olarak koyup geri kalanını optimize edebilmek güzel olurdu

  • Bu yaklaşımın karma tamsayılı programlama ile nasıl karşılaştırıldığını merak ediyorum. Fizik problemlerinde durum nasıl olur

    • Birçok problem iki şekilde de modellenebilir. MILP tarafında her zaman bir amaç fonksiyonu vardır ve kısıtlar da her zaman karar değişkenlerinin doğrusal birleşimleridir
      Gurobi inanması güç derecede hızlı olduğu için, çözüm almak adına problemi zorlayarak da olsa MILP kalıbına sokmaya değebilir
    • CP-SAT yalnızca tamsayılarla çalıştığı için fizik için çok uygun görünmüyor. Gerçek sayıları ölçekleyebilirsiniz ama kayan noktalı sayıları doğrudan ele almak kadar iyi değil
      CP-SAT'in avantajı, boolean ve tamsayı değişkenleri ile kısıtları MIP çözücülerine göre çok daha verimli işlemesi; bu özellikle all_different gibi yüksek seviyeli kısıtlarda belirginleşiyor
    • Genel olarak benzer olduklarını tahmin ediyorum. https://www.amazon.com/gp/product/1107658799/ bu konuda en son okuduğum kitaptı ve aynı fikirlerin çoğunu ele alıyor
      Özellikle bu yazıda bazı değerleri en aza indirmeye çalışılan kısımlar, bence doğrudan aynı şeyin yazılmış hali