SQL ile Aday, Açgözlüyle Karar

Bir önceki yazıda 7.730 ikili değişkenli bir karma tamsayılı program kurduk. Şimdi size bir şey itiraf edeyim: sahada gördüğüm zincirlerin çoğu bu işi öyle çözmüyor. SQL yazıyorlar. Bir sorgu, bir sıralama, bir döngü.

Bu yazı o yöntemin savunması değil, tarifi. Ama tarife geçmeden önce şunu söylemem lazım, çünkü optimizasyon anlatan yazılar genelde burayı atlar ve haksızlık eder: SQL ile çözmek aptalca bir tercih değildir. Üç sağlam gerekçesi var.

Birincisi, SQL zaten orada. Zincirin veri ambarı var, raporları oradan çıkıyor, ekip o dili konuşuyor. Yeni bir çözücü kurmak, lisansını almak, kütüphane sürümünü yönetmek gerekmiyor. İkincisi, okunabilir. Bir sorguyu planlama müdürü de okur, itiraz edeceği yeri gösterir; karma tamsayılı bir modelin çıktısına itiraz etmek için önce modeli anlamak gerekir. Üçüncüsü ve en önemlisi: her koşulda bir cevap üretir. Çözücü zaman limitine takılıp “en iyisini bulamadım” diyebilir; sıralama yapan bir sorgu her zaman bir liste verir.

Bu yazının sonunda bu yöntemin ne kadar iyi olduğunu ve tam olarak nerede para kaybettiğini TL’si TL’sine göreceğiz.

Adım 1: Adayı SQL bulur

Geçen yazının tezi şuydu: modelin en önemli kısmı yazmadığınız kısıtlardır. İş bilgisi çözücüye kısıt olarak değil, aday kümesinin tanımı olarak girer. İyi haber şu: o tanım zaten bir SQL sorgusudur.

Aşağıdaki sorgu Lumoda’nın veri setinde doğrudan çalışır ve boru hattının Python tarafıyla birebir aynı aday listesini üretir:

-- bt_* görünümleri: açık mağazalar ve ayıklanmış stok, satış, sevkiyat satırları
with karar as (select cast($karar as date) as t),

-- 1. Karar anı fotoğrafı, option düzeyinde: stoklu raflar ve set kırık mı?
foto as (
  select st.magaza_id, u.option_id,
         sum(st.adet) as stok,
         count(*) filter (where st.adet = 0 and u.beden_sira between 2 and 4) > 0 as kirik
  from bt_stok st join urun u using (urun_id), karar
  where st.tarih = karar.t
  group by 1, 2
  having sum(st.adet) > 0
),

-- 2. Hız: yalnız malın rafta olduğu haftaların ortalaması
stoklu_hafta as (
  select st.tarih as hafta, st.magaza_id, u.option_id
  from bt_stok st join urun u using (urun_id), karar
  where st.tarih >= karar.t - interval 8 week and st.tarih < karar.t
  group by 1, 2, 3
  having sum(st.adet) > 0
),
haftalik_satis as (
  select date_trunc('week', s.tarih) as hafta, s.magaza_id, u.option_id, sum(s.adet) as adet
  from bt_satis s join urun u using (urun_id), karar
  where s.tarih >= karar.t - interval 8 week and s.tarih < karar.t
  group by 1, 2, 3
),
hiz as (
  select sh.magaza_id, sh.option_id,
         coalesce(sum(hs.adet), 0)::double / count(*) as hiz
  from stoklu_hafta sh
  left join haftalik_satis hs
    on hs.hafta = sh.hafta and hs.magaza_id = sh.magaza_id and hs.option_id = sh.option_id
  group by 1, 2
),

-- 3. Soğumadaki raflar: son iki haftada mal varmış (depodan ya da mağazadan)
soguma as (
  select distinct sv.magaza_id, u.option_id
  from bt_sevkiyat sv join urun u using (urun_id), karar
  where sv.tarih > karar.t - interval 2 week and sv.tarih <= karar.t
),

-- 4. Verici adayı: stok var, seti kırık değil (orta bedenler rafta), cover eşiği geçiyor, soğumada değil
verici as (
  select f.magaza_id, f.option_id, f.stok, f.kirik, coalesce(h.hiz, 0) as hiz,
         case when coalesce(h.hiz, 0) > 0 then f.stok / h.hiz else 999 end as cover
  from foto f
  left join hiz h using (magaza_id, option_id)
),
verici_aday as (
  select v.* from verici v
  where v.cover >= 6
    and not v.kirik
    and not exists (select 1 from soguma s
                    where s.magaza_id = v.magaza_id and s.option_id = v.option_id)
),

-- 5. Alıcı adayı: seti kırık ya da stoksuz, ama satış hızı var
alici_aday as (
  select h.magaza_id, h.option_id, h.hiz
  from hiz h
  left join foto f using (magaza_id, option_id)
  where h.hiz >= 1
    and (f.kirik or f.stok is null)
),

urun_ozet as (
  select option_id, any_value(line) as line,
         any_value(liste_fiyati) as fiyat, any_value(alis_fiyati) as alis
  from urun group by 1
)

-- 6. Eşleştir ve ele: kendine gönderme yok, outlet malı vitrine gitmez
select v.magaza_id as verici, a.magaza_id as alici, v.option_id,
       v.stok as adet, v.hiz as hiz_verici, a.hiz as hiz_alici, u.fiyat, u.alis
from verici_aday v
join alici_aday a using (option_id)
join urun_ozet u using (option_id)
join bt_magaza m on m.magaza_id = a.magaza_id
where v.magaza_id <> a.magaza_id
  and (u.line <> 'Outlet' or m.tip = 'Outlet')
order by verici, alici, option_id

Seksen küsur satır ve tamamı iş kuralı. Dördüncü bloktaki cover >= 6 verici tanımı, beşincideki f.kirik or f.stok is null alıcı tanımı, altıncıdaki line <> 'Outlet' or m.tip = 'Outlet' ise ticaretin yasağı. Ali’nin ikinci sayısı, alıcıdaki azami cover, bu sorguda hiç görünmüyor: üçüncü kapı referans senaryoda kapalı olduğu için alici_aday yalnız kırık ya da stoksuz rafları topluyor. Depoda bu mantık birkaç fonksiyona bölünmüş durumda; burada okunabilirlik için tek sorguda topladım.

Sorgunun tek girdisi en üstteki $karar: hangi pazartesinin fotoğrafına bakılacağı. Hız, soğuma ve fotoğraf hep ona göre ölçülüyor, hiçbiri ondan sonrasına bakmıyor; karardan sonraki hiçbir satış ya da varış sorguya girmiyor. Sorgu ham tablolara da bakmıyor, bt_ ile başlayan görünümlere bakıyor: o pazartesi açık olan fiziksel mağazalar ve onların ayıklanmış satırları. Lumoda’nın verisinde de iki kez yazılmış satış satırı, hiç satılmadan bir pazartesi görünüp kaybolan hayalet stok var. Sizin verinizde zor olan büyük ihtimalle bu sorgu değil, o görünümlerin arkası olacak.

Dördüncü bloktaki and not v.kirik satırı, ikinci yazıda Pelin’in yakaladığı tuzağın koddaki karşılığı. Kırık setin satışı durur, cover’ı sonsuza gider; o satırı silerseniz sorgu kırık rafları en iyi verici diye sıralar ve terazi tersine çalışır.

İkinci bloğa da bir kez daha bakın: having sum(st.adet) > 0. Hızın yalnız stoklu haftalardan ölçülmesini sağlayan şey o tek satır. Onu silerseniz sorgu yine çalışır, hiçbir hata vermez ve stoksuzluktan satamamış her ürünü “yavaş satıyor” diye damgalar. Bu yazıdaki en tehlikeli satır o, çünkü kırık satırının hatası plana bakınca göze batar, bunun hatası batmaz.

Son satırdaki order by da süs değil; neden orada olduğunu sonraki yazıda anlatacağım.

Sorgu Lumoda’nın gerçek fotoğrafında 5.369 aday döndürüyor. “Birebir aynı” iddiasını da bir test tutuyor: test bu sorguyu yazının içinden okuyup çalıştırıyor ve Python tarafının listesiyle karşılaştırıyor. Yazı ile kod ayrışırsa test düşer.

Adım 2: Terazi puanı

Aday listesi elde. Şimdi her satıra bir puan lazım: ikinci yazının terazisi, üçüncü yazının $w$‘si:

Bunun için çözücüye gerek yok; sadece aritmetik. Sorgunun select satırına üç ifade eklemek ya da Python’da dört satır yazmak yeterli:

df["kazanc"] = np.minimum(df.adet, df.hiz_alici * H) * birim
df["kayip"] = np.minimum(df.adet, df.hiz_verici * H) * birim
df["tasima"] = p.adet_maliyeti_tl * df.adet
df["w"] = df.kazanc - df.kayip - df.tasima

birim burada liste fiyatı. Teraziyi kârla kurmak isteyen onu fiyat eksi alışla değiştirir; sorgunun alis kolonu bunun için orada. Üçüncü yazıda ölçtük: plan biraz değişiyor, kâr binde birkaç kıpırdıyor.

Dikkat: buraya kadar yaptığımız hiçbir şey optimizasyona özgü değil. Aday kümesi ve puanlama iki yöntemde de birebir aynı. Ayrım bir sonraki adımda başlıyor.

Adım 3: Açgözlü karar

En yüksek puanlı hareketi al, çakışanları ele, sıradakine geç. Tarifin tamamı bu; kodu da tarif kadar kısa:

sirali = adaylar.sort_values(
    by=["w", "verici", "alici", "option_id"],
    ascending=[False, True, True, True],
)
for satir in sirali.itertuples(index=False):
    if satir.w <= 0:
        break                                   # kalanların hepsi daha kötü
    sayac["pozitif"] += 1
    if (satir.verici, satir.option_id) in verilen:
        sayac["blok"] += 1
        continue                                # blok tek hedefe
    if kalan.get(satir.alici, 0) < satir.adet:
        sayac["kapasite"] += 1
        continue                                # alıcı kapasitesi
    verilen.add((satir.verici, satir.option_id))
    kalan[satir.alici] -= satir.adet
    sayac["secilen"] += 1
    secilen.append({k: getattr(satir, k) for k in HAREKET_KOLONLARI})

Üç kontrol, üç kısıt. sayac satırları yalnız sayıyor; aşağıdaki tablo onlardan geliyor. break ilk bakışta cesur görünüyor ama doğru: liste puana göre sıralı olduğuna göre ilk negatif puana geldiğinizde geri kalanların hepsi daha kötüdür.

Sıralamadaki verici, alici, option_id kuyruğu süs değil. Puanlar eşit çıktığında sıralamayı belirleyen şey olmazsa, aynı veriyle iki koşu iki farklı plan üretir. “Dün başka, bugün başka öneriyor” diyen bir sisteme de kimse güvenmez.

Gerçekte ne oldu

Sayılar, Lumoda’nın gerçek fotoğrafında:

Süre: 39,7 ms. Net kazanç: 32.680.688 TL.

O 1.895 sayısına bir saniye bakalım, çünkü açgözlü yöntemin doğası orada. Aynı bloğu isteyen birden çok mağaza var; en yüksek puanlı olan alıyor, öbür istekler kapıdan dönüyor. Yöntem dönen istekleri bir daha hiç düşünmüyor. Oysa belki de o bloğu ikinci sıradaki mağazaya verip, en yüksek puanlıya başka bir mağazadan mal bulmak toplamda daha iyiydi. Açgözlü yöntemin tanımı budur: her adımda o anın en iyisini seçer, seçiminin ileride ne kapattığına bakmaz.

Hemen altındaki 852 aynı hikâyenin ikinci yüzü. Puanı pozitif, bloğu henüz kimseye verilmemiş, ama alıcının kalan yeri yetmiyor: çoğu zaman önce seçilen bloklar yemiş, bazen mağazanın hiç yeri yok. Kapasite burada kâğıt üzerinde kalmıyor: karar anında 80 mağazanın 12’sinin hiç boşluğu yok. Döngü yer kalmayan alıcıya rastladığında “önceki seçimlerimden birini geri alsam bu daha iyi sığar mıydı?” diye soramaz; geri dönmek onun tarifinde yok.

Nerede para kaybediyor

Şimdi asıl mesele. Aynı veriyle çözücüyü de koşturalım ve iki planı yan yana koyalım:

Bu tabloya bakınca ilk sorduğum şey şuydu: aynı malı mı taşıyorlar? Hayır. İki plan 571 bloğu ortak taşıyor ama bunların 193’ünde alıcı farklı. Açgözlünün taşıyıp çözücünün dokunmadığı 15 blok var; çözücünün taşıyıp açgözlünün dokunmadığı 90 blok, toplam 12.580 adet.

Aritmetiği yapalım ve farkı ikiye ayıralım: hareketlerin $w$‘si ile rota masrafı.

Çözücü 22 rota az açıyor ve bunun değeri 11.000 TL. Kalan 3.242.435 TL hangi bloğun nereye gittiğinden geliyor. Döngü bir bloğu sırası geldiğinde en iyi hedefine veriyor; bu seçim hem o alıcının yerini yiyor hem o bloğu isteyen öbür mağazaların önünü kapatıyor. Sonra gelen, tek tek daha düşük puanlı ama birlikte daha değerli bloklar oraya sığmayabiliyor; döngü geri dönüp yeniden dağıtamıyor. Çözücü bütün blokları ve boşlukları aynı anda tartıyor. İzleri görünüyor: plan bittiğinde puanı pozitif bloklardan açgözlüde 270’i, çözücüde 194’ü alıcısına sığmıyor. Farkın ne kadarının yerden, ne kadarının blok çakışmasından geldiğini ayrıca ölçmedik.

Bir cümlede: fark kamyonlarda değil, hangi kolinin hangi rafa gittiğinde.

Kaba yama: minimum koli

Bir de dürüstçe anlatmam gereken bir yer var. Minimum koli kuralı (“iki adet için kamyon kaldırılmaz”) açgözlü akışa doğal olarak girmiyor, çünkü bir rotanın toplam yükü ancak bütün seçimler bittiğinde belli oluyor. Çözüm kaba: seçim bitince rotaların yüküne bakıp altında kalanları siliyoruz.

rota_adet = df.groupby(["verici", "alici"]).adet.transform("sum")
df = df[rota_adet >= p.min_koli].reset_index(drop=True)

Bunun neresi kötü? Silmekle yetiniyor, yerine bir şey aramıyor. O rotadaki hareketler iptal edildiğinde o bloklar boşa çıkıyor ama yöntem başa dönüp “madem bu rota açılmayacak, bu bloğu başka nereye verebilirim?” diye sormuyor.

Bu hafta yama 4 hareketi kesti: döngünün seçtiği 590 hareketten dördü, minimum koliyi dolduramayan rotalarda kaldığı için silindi ve yerlerine hiçbir şey konmadı. Dört hareket az görünüyor; asıl dert sayı değil, sessizlik. Böyle yamaların huyu budur: çoğu zaman hiçbir şey kesmez, “zaten devreye girmiyor” diye unutulur; veri ya da parametreler biraz değişince de kimseye haber vermeden keser. Bu hafta kesti ve plana bakan kimse fark etmezdi. Çözücü tarafında böyle bir yama yok: orada minimum koli modelin içinde bir kısıt satırı ve çözücü onu ihlal etmeden hareketleri birleştirme seçeneğini de değerlendiriyor.

Peki bu ne zaman yeter?

Rakamlara bakalım: açgözlü yöntem çözücünün bulduğu değerin %90,9’unu buluyor, hem de bin kattan daha kısa sürede ve sıfır kurulum maliyetiyle.

Bunu küçümsemek kolay ama yanlış olur. Bu yöntem şu koşullarda gerçekten doğru cevaptır: sabit maliyetler küçükse (rota masrafı toplamın yanında önemsizse), kararlar birbirini az kısıtlıyorsa, ekipte optimizasyon bakacak kimse yoksa ve “iyi” ile “en iyi” arasındaki fark bir toplantıda konuşulmaya değmeyecek kadar küçükse. Lumoda’nın bu haftası öyle değil. Aynı bloğu birden çok mağaza istiyor, alıcıların boşluğu bağlıyor ve aradaki fark %9,1: üç milyon TL’den fazla.

Ama dikkat: %90,9’u biz biliyoruz, çünkü diğerini de kurup ölçtük. Yalnızca açgözlü yöntemi çalıştıran bir zincir, sonucunun %90,9 mu yoksa %70 mi olduğunu bilemez. Sezgi burada işe yaramaz; kaybın büyüklüğü problemin şekline bağlıdır ve şekil her hafta değişir.

Sonraki yazıda aynı problemi çözücüyle kuracağız: PuLP ile modeli yazmak, CBC’yi koşturmak ve çözücü bir sınıra takıldığında ne yapılacağı. Altıncı yazıda ikisini bütün ölçütlerle yan yana koyacağız. Orada bir sürpriz var: kadranı çevirip parayı üçte iki büyüttüğünüzde, aradığını bulamayan müşteri bunu neredeyse hiç fark etmiyor 🙂