Son 50 Yılda Tamsayılı Doğrusal Programlama: Yakın Dönemdeki Pratik İlerlemeler — Anubis koruma sayfası gösteriliyor

 (inria.hal.science)
1 puan yazan GN⁺ 2025-06-16 | 1 yorum | WhatsApp'ta paylaş
  • Makale metni yerine Anubis bot doğrulama sayfası gösteriliyor; bu URL'de gerçek makale içeriği doğrudan görüntülenemiyor
  • Koruma sayfası, yapay zeka şirketlerinin agresif web scraping faaliyetlerinin sunucu kesintilerine ve kaynak erişiminin engellenmesine yol açabileceğini belirtiyor
  • Anubis, Hashcash’e benzer bir iş kanıtı talep ediyor; bireysel kullanıcılar için yük düşük kalırken, toplu scraping için kümülatif maliyetin artması hedefleniyor
  • Bu yöntem geçici bir çözüm; uzun vadede font render etme gibi ipuçlarıyla headless browser’ları tespit etmeye odaklanılıyor
  • Güncel JavaScript özellikleri gerektiğinden, JShelter gibi eklentiler etkinse erişim için ilgili alan adında devre dışı bırakılmaları gerekiyor

Anubis koruma sayfası gösteriliyor

  • Sayfa başlığı “Making sure you're not a bot!” ve ekranda hesaplanıyor durumu görünüyor
    • Zorluk 4
    • Hız 0kH/s
  • Sunucu yöneticisi, sunucuyu yapay zeka şirketlerinin agresif scraping faaliyetlerinden korumak için Anubis’i yapılandırdığı için bu sayfa gösteriliyor
  • Toplu scraping web sitesi kesintilerine neden olabilir; bunun sonucunda tüm kullanıcılar kaynaklara erişemeyebilir

İş kanıtı yöntemi ve erişim kısıtları

  • Anubis, Hashcash ailesinden bir iş kanıtı yöntemi kullanıyor
    • Tekil kullanıcıya binen ek yük ihmal edilebilir düzeyde
    • Toplu scraper’larda kümülatif maliyet büyüyerek scraping maliyetini artırıyor
  • Mevcut yöntem daha çok geçici bir çözüm niteliğinde
    • Amaç, font render etme biçimi gibi ipuçlarıyla headless browser’ları tespit etmek için zaman kazanmak
    • Meşru kullanıcı olma olasılığı yüksek durumlarda iş kanıtı sayfasını göstermemeye yöneliyor
  • Anubis güncel JavaScript özellikleri gerektiriyor
    • JShelter gibi eklentiler gerekli işlevleri devre dışı bırakabilir
    • Bu alan adında JShelter veya benzeri eklentilerin kapatılması gerekiyor

İlgili okumalar

1 yorum

 
GN⁺ 2025-06-16
Hacker News yorumları

  • Gurobi gibi ticari tamsayılı doğrusal programlama (ILP) çözücülerinin ücretsiz/açık kaynak olanlardan neden çok daha iyi olduğuna dair büyük resmi merak ediyorum.
    ILP’nin doğası gereği aşırı zor bir problem olduğu için en iyi çözücülerin, belirli alt problemler için büyük ölçekte biriktirilmiş sezgisellerden oluştuğunu ve kamusal alanda genel olarak iyi bir stratejinin henüz bulunmadığını mı merak ediyorum.

    • Başlıca neden, müşterilerle çok yakın çalışarak probleme özel hız iyileştirmeleri uygulamış olmaları. Üstelik bunu 10–20 yıldır yapıyorlar.
      Karma tamsayılı doğrusal programlamada (MILP), dallan-ve-sınırla yöntemi için iyi başlangıç noktaları bulup ağacı etkili biçimde budayan sezgiseller ve kesirli çözümleri keserek amaç değerini ve tamsayılılığı iyileştiren özel kesme düzlemleri önemlidir.
      Yöneylem araştırması araştırmacıları belirli bir problemi ele aldığında, kendi kesme düzlemlerini ve sezgisellerini yazarak Gurobi gibi genel amaçlı çözücüleri oldukça kolay biçimde geride bırakabilir. Çözücü şirketleri, doktora dereceli kişilerden ve araştırmacılardan oluşan ekipler istihdam ederek bu işi sürekli yapar; müşteri problemleri kümeleri üzerinde iyileştirmeleri ve regresyonları izler.
    • Büyük ticari çözücülerin, çözüm sürecindeki her şeyi gerçek problemlere göre ayarlamaya çok zaman ayıracak kaynakları ve iş birliği yapan müşterileri var. Sezgiseller bunun bir parçası; daha basit alt problemleri veya yaklaşıklamaları tanıyıp bunları tekrar tüm probleme yansıtmak da buna dahil.
      Açık kaynak çözücülerin birkaç şeyin birleşimiyle geride kaldığı görülüyor. Modern optimizasyon geliştirmesine giriş eşiği çok yüksek; hem matematik hem programlama tarafında anlamlı katkı verebilecek araştırmacı/geliştirici sayısı baştan az. Bu yeteneğe sahip olanlar için de para kazandıran yollar açık kaynak katkısından uzaklaştırıyor. Ayrıca açık kaynak projelerin doğası gereği “müşterilerin”, çözücüyü iyileştirmek için gereken örnekleri, performans verilerini ve profillemeyi geri sağlama olasılığı düşük.
      İstisnalar var ama geleneksel ticari çözücü geliştirme dışında olmak, otomatik olarak açık kaynak olmak anlamına gelmiyor. Örneğin Stanford’da geliştirilen SNOPT hâlâ ticari lisanslı. Akademideki çözücü çalışmaları, Clarabel gibi çoğu zaman belirli uygulama bağlamlarında yapılıyor; bu da problem ailelerinin daralma eğiliminde olduğu anlamına geliyor.
      Başka alanlarda büyük teknoloji şirketleri mevcut ticari projeleri satın alarak ya da rakiplerini dengelemek için açık kaynak projeleri fonlayarak darboğazı aşabildi. Çözücülerde Ceres gibi dar kapsamlı örnekler var; ancak genel amaçlı çözücü yığınının tamamını sıfırdan geliştirmeye yönelik yatırım muhtemelen fazla büyük görülmüştür.
    • Ticari çözücüler devasa bir teknik koleksiyonuna ve mevcut problemde hangi tekniğin işe yarayacağını saptayan iyi örüntü algılama mekanizmalarına sahip.
      Problem yapısını biliyorsanız bundan yararlanıp ticari çözücülerin performansını aşabilirsiniz. Ama rastgele bir problemde bunun olasılığı neredeyse yok.
    • “Çözücü, belirli alt problemler için büyük bir sezgisel topluluğudur” sözü, ILP gibi SAT ile eşdeğer NP-zor problemler için neredeyse kendiliğinden geçerli değil mi diye düşünüyorum.
    • Esas mesele ölçek ve hız. Örneğin çoğu kantitatif işlem şirketi mümkün olduğunca sık dev optimizasyonlar çalıştırır. Açık kaynak çözücüler bu tür problemleri çoğu zaman hiç çözemiyor; bellek yetersizliği istisnası gibi sonuçlarla karşılaşılıyor.

  • IBM’in “ILOG” karma tamsayılı doğrusal programlama kütüphanesiyle bir kaynak tahsis aracı yaptığımı belli belirsiz hatırlıyorum. Bizim 5 dakika içinde çözdüğümüz aynı problemi 20 yıl önce yapmış olsaydık hâlâ çalışıyor olacağını fark etmiştim.
    Saf hesaplama gücü yaklaşık 1000 kat artmış, algoritmalar da benzer ölçüde iyileşmişti; toplamda yaklaşık bir milyon kat daha iyi hâle geldiğini hatırlıyorum.
    Geleceği öngörürken üzerinde düşünmeye değer. Bu arada o “kaynaklar” elmaslardı.

  • Bunların pratikte nasıl kullanıldığını merak ediyorum. Sayısal optimizasyon uygulayınca, veri odaklı yaklaşımlarda sık görülen güven ve kötü veri gibi sorunlar yüzünden çoğu zaman başarısız olduğu; sonunda da önemli birinin ne yapılacağına sezgileriyle karar verdiği bir tablo geliyor aklıma.

    • İş yerinde yığının tamamında çözücüler kullanıyoruz. Ev bataryalarını ve elektrikli araçları en iyi şekilde zamanlayan bir çözücü; bu evlerden yüz binlercesini portföy olarak en iyi şekilde zamanlayan bir çözücü; o portföyü en iyi şekilde alıp satan bir çözücü var.
      AB elektrik spot fiyatları her gün tek bir dev çözücü çalıştırmasıyla belirleniyor. Euphemia’yı ararsanız nasıl çalıştığına dair yazılar bulabilirsiniz.
      Optimize edilecek net bir hedefin olduğu ve gerçek paranın söz konusu olduğu çoğu alan çözücülerle dolu.
    • FMCG şirketlerinde bunlar gerçekten bu amaçlarla kullanılıyor. Satış temsilcileri ve teslimat rota planlaması, üretim için makine·iş gücü·malzeme kaynaklarının zamanlanması, depo dağıtım merkezlerindeki stok seviyelerinin optimizasyonu gibi işler var.
      Stok tarafı, talep tahmini zor olduğu için tamamen otomatikleşmiş değil.
    • Vaka çalışmalarını okuyabilirsiniz.
      Gurobi vaka çalışmaları: https://www.gurobi.com/case_studies/
      Bazı CPLEX vaka çalışmaları: https://www.ibm.com/products/ilog-cplex-optimization-studio/...
      Hexaly, eski adıyla LocalSolver, vaka çalışmaları: https://www.hexaly.com/customers

  • Gurobi’nin epey pahalı olduğunu duydum. Fiyat bilgisi paylaşabilecek biri var mı merak ediyorum.

    • Fiyat bilgisi gizli olduğu için paylaşamam; ama sadece MIP ile oynamak istiyorsanız çok pahalı üç büyük çözücü olan XPRESS, Gurobi ve CPLEX’i satın almanız gerekmez. Genellikle öğrencilere ücretsiz sunulurlar.
      Açık kaynak olan veya ticari olmayan kullanım için ücretsiz olan en az iki iyi MIP çözücü var:
      https://highs.dev/
      https://www.scipopt.org/
    • Duyduğuma göre, elbette doğrulayamam, fiyatlandırma kademesi fiilen tek bir şey: “bizimle iletişime geçin”; sonra o sırada ne kadar para kazandığınızı anlayıp bir kısmını istiyorlar.
    • Bunun neden bu kadar derin saklanan bir sır olduğunu düşündüğünüzü bilmiyorum. Çekirdek sınırlamalı lisans için koltuk başına kabaca 10 bin dolar.
    • Yavaşça yanlış kararlar almaktan çok daha ucuz. GLPK gibi ücretsiz çözücüler küçük problemler için iyidir ama birçok iş problemi, premium bir çözücüye ödeme yapmadığınız sürece gereken süre içinde neredeyse çözülemez. Gurobi bunların en iyisi.
    • Yaklaşık 10 yıl önce en son kontrol ettiğimde, birden çok kullanıcının sunucuda kullandığı tam lisans yaklaşık 100 bin dolardı. Tam koltuk sayısı veya sunucu sayısı sınırını hatırlamıyorum.
      Sektördeki pek çok kişi için kesinlikle parasını fazlasıyla hak ettiğini eklemek isterim.

  • 1990’larda öğrenme amacıyla Maple’da Gomory kesme hiperdüzlemlerinin bir sürümünü uyguladığımı hatırlıyorum. Gerçek kullanım için değildi. Alan epey ilerlemiş gibi görünüyor.
    “1990’ların başında bir LP’yi çözmek için çalışma süresi iki ay gerekiyorsa, bugün 1 saniye bile sürmüyor. Bixby yakın zamanda 1990’dan 2020’ye kadar iki MILP çözücüsü olan CPLEX ve Gurobi’nin makineden bağımsız performansını karşılaştırıp neredeyse 4×10^6 kat hız artışı bildirdi.”

  • Bu tür problemlere yönelik makine öğrenmesi/yapay zeka tabanlı yaklaşımların epey eksik olduğu hissine kapılıyorum. Küçük problemleri çözmeye çalışan pek çok pekiştirmeli öğrenme/graf sinir ağı makalesi örneği gördüm ama çoğu zaman sonunda en iyi seçenek Gurobi lisansı alıp çalıştırmak gibi görünüyor.
    Yakın zamanda atölye çizelgelemesine yakın bir çizelgeleme optimizasyonu üzerinde çalıştım; pekiştirmeli öğrenme kullanan örnekler olsa da yeterli görünmüyor. Büyük problemlerde makul çözümler elde etmek için evrimsel algoritmalara bel bağlamak zorunda kaldım.
    Problemi iyi biçimde formüle edebiliyorsanız, yöneylem araştırması tarzı bir yaklaşım kullanmak her zaman daha verimli midir, emin değilim.

    • Probleme bağlı. Güvenlik kısıtlı birim devreye alma problemi, hangi santralin ne zaman açılacağına karar verme problemidir; inanılması güç derecede karmaşıktır ama Gurobi gibi MILP çözücüleri MIP aralığı içinde küresel optimumu hızla bulabilir.
      Bir genetik algoritma da oluşturabilirsiniz ama yerel minimumlara takılmamış bir yanıt vereceğine dair garanti yoktur. Hızlı çalıştırılabileceği varsayımı da gerekir. Sinir ağı da muhtemelen optimumdan daha kötü olacaktır.
    • SAT, standart bir sembolik yapay zeka (GOFAI) problemidir ve elbette makine öğrenmesi ailesinden bir programlama diliyle SAT çözücüsü yazabilirsiniz. Bu anlamda makine öğrenmesi/yapay zeka yaklaşımının oldukça uygulanabilir olduğunu düşünüyorum.

  • “1988’den 2004’e kadar donanım 1600 kat hızlandı, LP çözücüleri ise 3300 kat hızlanarak kümülatif hızlanma katsayısını 5 × 10^6’nın üzerine çıkardı. Üstelik bu zaten 20 yıl önceydi!”
    “Yazarlar 2001 ile 2020 arasında ticari MILP çözücülerinde 1000 kat hız artışı gözlemledi. Bunun 50 katı algoritmalardan, 20 katı ise daha hızlı bilgisayarlardan kaynaklanıyor.”
    Bilişimin alt alanlarına göre bu tür hız artışı katsayılarının toplanıp algoritma iyileştirmeleri ile daha hızlı bilgisayarların katkılarına ayrıştırılıp ayrıştırılamayacağını merak ediyorum.
    Derleyicilerde “Proebsting yasası” vardır. Bu yasa, derleyici ilerlemesinin 18 yılda bir bilgi işlem performansını ikiye katladığını söyler.

  • Başlığa [pdf] [2024] eklemek iyi olurdu.