- Tamsayılı doğrusal programlama (MILP) birçok endüstride temel bir araç haline geldi
- En yeni çözücülerin hesaplama verimliliğindeki artış sayesinde, geçmişte çözülmesi zor olan problemlerde bile artık en iyi çözüm hızla bulunabiliyor
- Bu yazı, MILP çözüm yöntemlerindeki son pratik gelişmelere ve bilgi işlem performansındaki iyileşmelere odaklanarak açıklıyor
- Başlıca yöntemler olarak branch-and-cut, Dantzig-Wolfe ayrıştırması, Benders ayrıştırması tanıtılıyor
- MILP alanındaki süregelen zorluklar ve gelecekteki araştırma fırsatları özetleniyor
Giriş
- Karma tamsayılı doğrusal programlama (MILP), yöneylem araştırmasında vazgeçilmez bir araçtır ve çok çeşitli endüstriyel alanlarda başarıyla kullanılmaktadır
- Modern MILP çözücüleri, geçmişte imkânsız görülen büyük ölçekli problemler için artık saniyeler içinde en iyi çözümü arayabiliyor
- Bu sayede taşımacılık, tedarik zinciri, gelir yönetimi, finans, telekomünikasyon, imalat gibi pek çok alanda MILP kullanımı genişledi
- Ancak hâlâ çözülmemiş problemler ve yeni zorluklar bulunduğundan, MILP araştırmaları istikrarlı biçimde aktif şekilde sürüyor
Ana İçeriğe Genel Bakış
- Bu makale, MILP çözüm yöntemlerindeki son gelişmeler ve pratik performans iyileştirmeleri üzerine odaklanarak, her tekniğin gerçek hesaplama performansına nasıl katkı sağladığını inceliyor
- Geniş literatür içinden, özellikle gerçek hesaplamalı deneylere dayanan çalışmalar öncelikli olarak ele alınıyor
- Tartışma, MILP çözüm yöntemlerinin üç temel alanı etrafında yapılandırılıyor
- Branch-and-Cut yöntemi: düğüm dallandırma teknikleri ile cutting plane tekniklerini birleştiren temsilî bir MILP çözüm yaklaşımıdır
- Dantzig-Wolfe ayrıştırması: büyük ölçekli problemleri daha küçük alt problemlere bölerek verimli biçimde işleyen bir ayrıştırma yaklaşımıdır
- Benders ayrıştırması: değişkenleri ve kısıtları ayırıp yinelemeli olarak çözerek karmaşık yapılarda hesaplama yükünü azaltan bir yöntemdir
Sonuç: Zorluklar ve Gelecek Perspektifi
- Makalenin son bölümünde, hâlâ devam eden MILP zorlukları ve gelecekteki araştırma fırsatları ele alınıyor
- Giderek daha karmaşık hale gelen gerçek endüstriyel problemler, verinin büyümesi ve çözücü performansının sınırları bundan sonraki başlıca araştırma konuları olacak
- Önümüzdeki dönemde MILP alanının algoritmalardaki ilerleme, donanımdaki gelişmeler ve yeni uygulama alanlarının genişlemesiyle birlikte büyümeyi sürdürmesi bekleniyor
1 yorum
Hacker News görüşleri
Birisi, Gurobi gibi ticari ILP çözücülerinin neden ücretsiz/açık kaynak çözücülerden çok daha iyi olduğunu açıklayıp açıklayamayacağını merak ediyor; bunun ILP'nin özündeki zorluktan mı kaynaklandığını, yoksa en iyi çözücünün belirli alt problemler için devasa bir sezgisel yöntemler kümesi olmasından mı ileri geldiğini, dolayısıyla genel olarak “iyi” stratejilerin hâlâ kamuya açık alana çıkmadığını soruyor
Ticari çözücülerin çoğu müşterilerle yakın çalışarak probleme özgü hızlandırma teknikleri uygular ve 10-20 yılda birikmiş ciddi bir bilgi birikimine sahiptir; MILP alanında iyi sezgisellerin (branch-and-bound başlangıç noktası seçimi, etkili ağaç budama) ve özel kesmelerin (kısmi çözümleri verimli biçimde dışlama) önemine dikkat çekiliyor. Ayrıca OR araştırmacıları problemi kendileri seçip özel kesmeler ve sezgiseller yazdığında çoğu zaman ticari çözücülerden daha iyi sonuçlar alabiliyor; ancak çözücü şirketleri bunu tutarlı biçimde hayata geçirmek için doktora düzeyinde araştırma ekipleri istihdam ediyor ve çok sayıda müşterinin gerçek problem verisiyle iyileştirmeleri takip ediyor
Ticari çözücüler, gerçek müşteriler ilgilenip destek verdiği için problem çözme performansını ayarlamaya çok büyük zaman ve kaynak ayırabiliyor. Bu, sezgisellerin yanı sıra basit alt problemleri veya yaklaşık problemleri tanıyıp bunların sonuçlarını ana probleme geri besleme sürecini de içeriyor. Açık kaynak çözücüler ise sınırlı; çünkü (1) son teknoloji optimize edici geliştirmeye giriş bariyeri çok yüksek (hem matematikte hem kodlamada yetkin kişi az), (2) bu seviyede yeteneği olanlar genelde daha çok para kazandıran kariyerlere gidiyor, (3) açık kaynak yapısında müşteriler iyileştirme için örnek vakalar, performans verisi, profilleme vb. neredeyse hiç sağlamıyor İstisna olarak SNOPT gibi ticari amaçlı ama geleneksel olmayan ticari geliştirme örnekleri var; akademik çözücüler ise belirli uygulama alanlarına odaklandığından genellikleri düşük. Diğer alanlarda Google gibi büyük şirketler satın alarak veya destekleyerek ekosistemi büyütebiliyor, ancak çözücü alanında en baştan tüm yığını kurmak için gereken yatırım yükü fazla büyük
Ticari çözücüler, gerçekten çok çeşitli hileler ve örüntü tespit mekanizmaları sayesinde, probleme göre hangi hilelerin etkili olacağını anlayabiliyor. Problem yapısını iyi biliyorsanız ticari çözücülerden de hızlı bir şey yapabilirsiniz, ama rastgele bir problemde şansınız neredeyse yok
“Çözücü = özelleşmiş alt problemlere yönelik çeşitli sezgiseller kümesi” iddiası var; NP-Hard problemler için neredeyse her şeyin zaten böyle bir yapıda olduğu belirtiliyor. ILP, SAT ile eşdeğer olduğundan aynı durum burada da geçerli
Ticari ölçek ve hız konusu var; kuant trading şirketlerinin çoğu çok büyük optimizasyon problemlerini mümkün olduğunca sık çalıştırıyor ve açık kaynak çözücüler çoğu zaman ya hiç çözemiyor ya da bellek yetersizliği yaşıyor. Aradaki fark o kadar büyük
IBM'in ILOG MILP kütüphanesiyle kaynak tahsis aracı yaparken yaşanan deneyim hatırlatılıyor; benzer bir problem 20 yıl önce çözülseydi, bugün 5 dakikada biten şey o zaman hâlâ çalışıyor olurdu. Bilgisayar performansı bin kat arttı, algoritmalar da bin kat iyileşti; toplamda bir milyon katlık gelişim var. Geleceği tahmin ederken üzerinde düşünmeye değer bir nokta. Bu arada buradaki “kaynak”, elmaslardı
Bunun pratikte gerçekten nasıl kullanıldığı merak ediliyor; sayısal optimizasyonun, veri temelli genel sınırlamalar (güven, veri sorunları vb.) yüzünden sonunda önemli bir insanın “içgüdüsüyle” karar verdiği bir şeye dönüşmediği soruluyor
Bir şirkette tüm yığın boyunca çözücüler kullanılıyor: ev tipi batarya ve EV zamanlama optimizasyonu, yüz binlerce haneden oluşan portföyün en iyi şekilde planlanması ve o portföyün alım satımı bile çözücülerle yapılıyor. AB elektrik spot fiyatları da Euphemia adlı tek dev çözücünün çalıştırılmasıyla belirleniyor. Pratikte parayla bağlantılı, net bir optimizasyon hedefi olan her alanda çözücüler yaygın kullanılıyor
Bir FMCG şirketindeki gerçek kullanım örnekleri: (1) satış personeli ve teslimat rotası planlama, (2) üretim için makine, iş gücü ve malzeme zamanlama, (3) depo/dağıtım merkezi için doğru stok seviyesini belirleme. Talep tahmininin zorluğu nedeniyle tam otomasyon sağlanamıyor
Bakılabilecek vaka çalışmaları bağlantıları paylaşılıyor: Gurobi vaka çalışmaları, CPLEX vaka çalışmaları, Hexaly(eski adıyla LocalSolver) vaka çalışmaları
Gurobi'nin epey pahalı olduğunun duyulduğu, gerçek fiyat bilgisinin paylaşılıp paylaşılamayacağı soruluyor
Net fiyatlar gizli, ancak amaç MIP pratiği yapmaksa XPRESS/Gurobi/CPLEX gibi ticari çözücüleri satın almak yerine öğrenciye yönelik ücretsiz lisanslar veya ticari olmayan ücretsiz/açık kaynak MIP çözücüleri kullanmak öneriliyor; örneğin: HiGHS, SCIP
Duyulana göre fiyatlandırma “arayın, pazarlık yapalım” düzeyinde ve gerçekte müşterinin ne kadar para kazandığına bakıp ona göre bedel belirleniyor
Yavaş ve alt optimal karar vermekten çok daha ucuz olduğu vurgulanıyor. Küçük problemler için ücretsiz çözücüler (GLPK vb.) yeterli olabilir, ancak iş dünyasındaki büyük problemler için zamanında çözüm almak ücretsiz çözücülerle neredeyse imkânsız; bu yüzden premium çözücüler fiyatını hak ediyor
Yaklaşık 10 yıl önce, birden fazla sunucu lisansı için yaklaşık 100 bin dolar seviyesinin hatırlandığı; tam kullanıcı veya sunucu sınırlarının hatırlanmadığı, ancak sektörün bu değeri rahatça kabul ettiği belirtiliyor
Gurobi, saatlik ücretlendirmeyle çalışan bir bulut hizmeti de sunuyor ve akademik olmayan lisanslar oldukça pahalı
1990'larda Gomory kesme hiper düzlemlerini doğrudan uygulamış olma deneyimi anlatılıyor; alanın bu sürede ne kadar ilerlediği şaşırtıcı bulunuyor. Eskiden bir LP problemini çözmek iki ay sürerken şimdi 1 saniye yeterli. Bixby'nin çalışması, 1990-2020 arasında CPLEX ve Gurobi'nin makine performansından bağımsız olarak neredeyse 4 milyon kat hızlandığını bildiriyor
1988-2004 arasında donanım 1600 kat, LP çözücüleri 3300 kat hızlandı; o dönemde bile toplam birikimli hızlanma 5 milyon katı aşıyordu. 2001-2020 arasında ticari MILP çözücüleri de 1000 kattan fazla hızlandı (algoritma 50, bilgisayar 20). Bu alanlardaki hızlanma verilerini algoritma ve bilgisayar katkısı diye ayırıp toplamanın ilginç olacağı söyleniyor; derleyici alanında da “Proebsting yasası” gibi, 18 yılda derleyici gelişiminin işlem gücünü 2 kat artırmaya denk geldiğini söyleyen sonuçlar var
ML/AI tabanlı yaklaşımların bu problemlerde şaşırtıcı biçimde çok kullanılmadığı hissi var; RL/GNN kullanan küçük ölçekli denemeler içeren makaleler olsa da sonunda Gurobi lisansı almanın en iyi yol gibi göründüğü söyleniyor. Yakın zamanda zamanlama optimizasyonu yaparken RL örnekleri görüldüğü ama gerçek performansın yetersiz kaldığı, büyük problemler için evrimsel algoritmaların daha uygun olduğu; sonuçta problem formülasyonu iyi kurulabiliyorsa OR tabanlı yaklaşımın en verimlisi olduğu düşünülüyor
Problem türüne göre değişir; örneğin enerji santrali aç/kapat kararı (unit commitment) son derece karmaşıktır, ancak bir MILP çözücüsü global optimumu hızla arayabilir. Genetik algoritmaların yerel minimumlardan çıkma garantisi yoktur ve çalıştırmaları da yavaş olabilir; sinir ağları da her zaman alt optimal kalır
SAT, geleneksel bir GOFAI problemidir ve ML ailesindeki her dille de SAT çözücüsü yazılabilir; hatta “ML/AI” yaklaşımı aslında gayet uygulanabilir deniyor
Başlığa pdf ibaresi eklenmesinin iyi olacağı yönünde yorum yapılıyor
İlgili bağlantının pdf değil, özete (abstract) gittiği belirtiliyor
Doğrudan makalenin pdf referansı eklenebiliyor: https://inria.hal.science/hal-04776866v1/document
Integer linear programming'in karmaşık görünmediği yönünde bir görüş var
Grafik tepe noktası 3-renklendirme (G3C), hem NP hem NP-Hard olduğu için NPC'dir; genel ILP çözülürse G3C'nin de çözülebileceği bilinir. SAT de NP-Complete'tır; SAT çözülürse G3C de çözülebilir, dolayısıyla G3C çözülebiliyorsa tamsayı çarpanlara ayırma (FAC) da mümkün olur. FAC NPC değildir ama bugünkü bilgi işlem ortamında son derece kritiktir. Yani keyfi bir ILP'yi çözebilmek, başlıca kriptografik algoritmaları kırmayı mümkün kılabilir; bu da ILP'nin ne kadar çetin bir problem olduğunu gösterir. İnsanların sık karıştırdığı nokta ise NPC problemlerde rastgele örneklerin çoğunun genelde kolay çözülmesidir; zor örneklerin oranı, problem boyutu büyüdükçe aksine azalır
Gezgin satıcı problemi (Travelling Salesperson Problem, TSP) de ILP olarak kodlanabilir; bu da ne kadar zorlayıcı olduğunu gösterir
Koşulları en iyi sağlayan tamsayıyı bulmanız gerekir; kulağa reel sayılarla benzer gelse de özünde tamamen farklıdır. Genel amaçlı bir çözüm yoktur, yalnızca özel durumlar için geliştirilmiş (çok iyi) sezgiseller vardır
Lineer programlamadan daha zor bir problemdir
Ya da oldukça gerçekçi bir problem olarak görülebilir