Problemi tarif etmek ile çözmek ayrı iştir: Meta’nın açık kaynak atama çözücüsü Rebalancer
Open-Sourcing Rebalancer: A Generic, High-Performance Library for Solving Assignment Problems
Elinde bir nesne kümesi ve bir kutu (bin) kümesi var; nesneleri, belirli kısıtları sağlayarak ve bazı hedefleri optimize ederek kutulara nasıl atarsın? Bu soru Meta'nın altyapı yığınının her katmanında çıkıyor: donanım yerleşimi (rafları elektrik arıza alanlarına yaymak), servis yerleşimi (sunucuları servislere atamak), görev yerleşimi (görevleri sunuculara atamak) ve trafik yönlendirme (milyarlarca kullanıcının trafiğini coğrafi olarak dağılmış veri merkezlerine yollamak).
Yeniden kullanılabilir bir çerçevenin iki zorluğu var: kullanılabilirlik (pratisyenler gerçek hayat politikalarını biçimsel optimizasyonun gerektirdiği kesin formüllere çevirmekte zorlanıyor) ve ölçeklenebilirlik (NP-zor problemleri ticari çözücüler verimli çözemiyor). Rebalancer, problemin belirtimini çözümünden ayırarak ikisini birden ele alıyor. Problem; nesneler, kutular, kısıtlar ve hedeflerle tanımlanıyor, sonra bir ifade grafiğine (yönlü döngüsüz graf) çevriliyor. Çözücü bu grafikten yararlanarak ya yerel arama sezgiseli tasarlıyor ya da ticari (FICO Xpress, Gurobi) veya açık kaynak (HiGHS) bir çözücüyle çözülebilen karma tamsayılı programlama (MIP) modeli kuruyor.
Belirtim dili üç adımda soyutlama seviyesini yükseltiyor: temel modelleme yapıları (boyutlar, bölümler, kapsamlar, kullanım), bu yapılar üzerinde yaygın ifadeler (SUM, MAX gibi toplulaştırmalar) ve düzinelerce hazır hedef ve kısıtı sunan üst düzey ‘spec’ API’si (‘her rafta tek iş tipi olsun’ için GroupCountSpec, dengeli dağılım için BalanceSpec gibi). Spec’ler, yeniden kullanılabilen hazır tarifler.
İki çözüm tekniği var. Optimal çözücü ifade grafiğini MIP çözücülere verir; ama her nesne için bir ikili karar değişkeni gerektirdiğinden model boyutu en kötü durumda O(nesne × kutu) ile ikinci dereceden büyür ve en büyük problemler hiçbir MIP çözücüye sığmaz. Yerel arama çözücüsü doğrudan ifade grafiği üzerinde çalışır: mevcut atamanın çevresindeki komşulukta bazı nesneleri başka kutuya taşıyıp en çok iyileşen kısıt ihlal etmeyen hamleyi uygular. Komşuluk büyüklüğü en kötü durumda O(nesne + kutu), yani bellek sorunu olmadan çok büyük problemleri modelleyebilir; saniyede milyonlarca değerlendirme yapılabiliyor.
Öne çıkanlar
- Belirtim (ne istiyorum?) ile çözüm (nasıl bulurum?) ayrılınca aynı problem farklı çözücülerle çözülebilir.
- Hazır ‘spec’ler domain bilgisini yeniden kullanılabilir hâle getiriyor: her ekip aynı kısıtı yeniden yazmıyor.
- Kesin çözüm ile ölçek arasında takas: optimal çözücü küçük/orta, yerel arama çok büyük problemler için.
- Önce başlangıç ataması ve durma koşulu verilir; çözücü ‘yeterince iyi’ bir çözüme zamana bağlı yaklaşır.
Neden önemli?
Birçok altyapı sorunu (iş zamanlama, yük dengeleme, kapasite planı) aslında atama problemidir ama ad hoc kodla çözülür. Problemi deklaratif tarif edip çözücüyü değiştirebilmek, SQL’in veri sorgularına getirdiği şeyin optimizasyondaki karşılığı.
Sende karşılığı
Hemen deneyebileceğin yer: scipy.optimize.milp (arka planda HiGHS kullanır) ile küçük bir atama problemi çözmek. Örneğin Tradebot’ta sermayeyi belirli kısıtlarla (varlık başına tavan, toplam risk limiti) varlıklara dağıtmak ya da Mobit’te zamanlanmış işleri çalışanlara eşit yükle dağıtmak. Daha önemlisi tasarım dersi: kısıtları kodun içine ‘if’ olarak gömmek yerine, bildirimsel bir listede (‘her sunucuda en fazla 3 iş’, ‘iki kopya aynı rafta olmasın’) tutarsan hem testi hem değişimi kolaylaşır.
Sözlük
- assignment problem atama problemi
- Nesneleri kısıtlar altında, bir hedefi optimize edecek şekilde kutulara yerleştirme problemi.
- mixed integer program (MIP) karma tamsayılı program
- Bazı değişkenlerin tam sayı olmak zorunda olduğu doğrusal optimizasyon problemi.
- local search yerel arama
- Mevcut çözümü küçük değişikliklerle iyileştirerek ilerleyen sezgisel arama.
- fault domain arıza alanı
- Tek bir arızanın birlikte etkileyebileceği bileşenler grubu (aynı raf, aynı elektrik hattı gibi).