Stokastik Karma Tamsayılı Programlama — Ayrık ve Sürekli Kararlarla Belirsizlik Altında Optimizasyon
- Ortaya koyan
- Birge, J. R.; Louveaux, F.; Sen, S.
- Yıl
- 1990s–2000s
- Tür
- Stochastic optimization model
- Aile
- Simulation / optimization
Bu metin makine çevirisidir ve henüz incelenmedi. Asıl metni İngilizce oku
Ne işe yarar?
Stokastik Karma Tamsayılı Programlama (SMIP), maliyetler, talepler, kapasiteler gibi temel parametrelerin belirsiz olduğu ve bir senaryo kümesi üzerinde olasılık dağılımları olarak modellendiği durumlarda ikili, tamsayılı ve sürekli kararların en iyi karışımını bulan bir optimizasyon çerçevesidir.
Kombinatoryal kısıtlamalara uyarken belirsizliğe karşı koruma sağlayan senaryo ağaçlarını veya beklenen değer hedeflerini gömerek klasik Karma Tamsayılı Programlamayı (MIP) genişletir.
Yöntemin mantığı
Birçok gerçek planlama problemi evet/hayır veya tam sayı seçimlerini zorlar (bir tesis inşa etmek veya etmemek, belirli sayıda araç atamak gibi), ancak gelecek belirsizdir. SMIP bunu, bir dizi olası gelecek senaryosunu dikkate alarak ve tüm senaryolarda beklenen maliyeti en aza indiren veya beklenen faydayı en üst düzeye çıkaran ilk aşama taahhütlerini (belirsizlik ortaya çıkmadan önce) seçerek resmileştirir. Tamsayı kısıtlamaları problemi kombinatoryal olarak zorlaştırır, ancak ayrıştırma algoritmaları, büyük örnekleri çözülebilir hale getirmek için senaryo yapısını kullanır.
Tarih
Stokastik programlama, Dantzig (1955) ve Beale (1955) ile iki aşamalı LP olarak ortaya çıkmıştır. Karma tamsayı uzantısı, 1990'larda Laporte ve Louveaux (1993) tarafından tamsayı başvuru için L-şekilli yöntem uyarlamaları ve Birge ve Louveaux'nun 1997 tarihli ders kitabındaki kapsamlı ele alışla belirgin bir şekilde ortaya çıkmıştır. Sen ve Higle'nin C3/D2 algoritması (2005), ölçeklenebilir SMIP çözücülerini geliştirerek alanı yöneylem araştırması içinde olgun bir disiplin olarak kurmuştur.
Ne zaman kullanılır?
Kararlar ayrık veya ikili seçimler içerdiğinde (yatırım yap/yapma, açılacak birim sayısı) ve temel girdi parametreleri ölçülebilir olasılık dağılımlarıyla gerçekten belirsiz olduğunda SMIP kullanın. Talep belirsizliği altında tedarik zinciri ağı tasarımı, enerji kapasitesi genişletme, sağlık tesisi planlaması ve afet müdahale ön konumlandırması için idealdir. Tüm kararlar sürekli olduğunda (bunun yerine stokastik LP kullanın), belirsizlik anlamlı bir şekilde dağılımlar olarak nicelendirilemediğinde, belirsizliği temsil etmek için gereken senaryo sayısı çözülemez model boyutlarına yol açtığında ve ayrıştırma mevcut olmadığında veya gerekli karar kalitesi için simülasyon tabanlı bir sezgisel yeterli olduğunda kullanmayın.
Sınırlar ve dikkat edilmesi gerekenler
- Hesaplama karmaşıklığı, senaryo sayısı ve tamsayı değişkenleriyle kombinatoryal olarak artar; büyük örnekler, etkili ayrıştırma olmadan çözülemez olabilir.
- Açık olasılık dağılımları veya senaryo kümeleri gerektirir — yanlış belirtilmiş belirsizlik modelleri, örnek dışı performansı kötü olan çözümlere yol açar.
- İki aşamalı formülasyonlar, çok dönemli kararları aşırı basitleştirebilir; çok aşamalı SMIP önemli ölçüde daha zordur.
- Tamsayı ikinci aşama başvuru, standart Benders kesmelerinin kullandığı dışbükeyliği bozar ve özel tamsayı L-şekilli kesmeler gerektirir.
Kaynak metnin koşulları, bağımsız bilimsel inceleme veya analiz motoru doğrulaması yerine geçmez.
Güçlü yönleri
- Belirsizlik altında kombinatoryal ayrık kararları tek bir tutarlı optimizasyon modelinde ele alır.
- Tüm senaryolarda beklenen performansı dengeleyen korumalı ilk aşama planları üretir.
- VSS ve EVPI metrikleri, stokastik modellemenin değeri için şeffaf gerekçe sağlar.
- Ayrıştırma algoritmaları (L-şekilli, aşamalı koruma) büyük senaryo kümelerine ölçeklenebilir.
- Ticari çözücülerde (CPLEX, Gurobi) ve modelleme dillerinde (AMPL, Pyomo) geniş çapta desteklenir.
Uygulama alanları
- Belirsiz müşteri talepleri ve ikili tesis konumlandırma kararları ile tedarik zinciri ağı tasarımı.
- Belirsiz yenilenebilir üretim ve yük artışı altında elektrik gücü kapasite genişletme planlaması.
- Epidemiyolojik belirsizlik altında sağlık sistemi kaynak tahsisi (tamsayı personel, ikili klinik açılışları).
- Afet senaryoları öncesinde insani lojistik için ayrık yardım malzemelerinin ön konumlandırılması.
- Piyasa belirsizliği altında işlem maliyetleri ve tamsayı parti büyüklüğü kısıtlamaları ile finansal portföy optimizasyonu.
- İkili atama değişkenleri ile belirsiz uçuş gecikmeleri altında havayolu mürettebatı çizelgeleme.
Nasıl çalışır?
Nasıl çalışır?
Karar değişkenlerini tanımlayın: belirsizlik ortaya çıkmadan önce alınan ilk aşama kararları x (aralarında tamsayılar ve/veya ikililer bulunur) ve xi senaryosu gerçekleştikten sonra alınan ikinci aşama başvuru değişkenleri y(xi). Amaç katsayılarını, kısıt matrislerini ve belirsiz parametreler için olasılık dağılımını veya ayrık senaryo kümesini belirtin.
Temel dağılımı yaklaşık olarak temsil eden, ilişkili {p_1, ..., p_S} olasılıkları ile sonlu bir {xi_1, ..., xi_S} senaryo kümesi oluşturun. Senaryolar geçmiş verilerden, uzman görüşlerinden, Latin hiperküp örneklemesinden veya moment eşleştirme yöntemlerinden türetilebilir. Senaryo kalitesi, çözüm kalitesini doğrudan etkiler.
Deterministik eşdeğeri formüle edin: c'x + sum_s p_s Q(x, xi_s) ifadesini ilk aşama kısıtlamaları ve tamsayılık koşulları altında minimize edin. Q(x, xi_s), ikinci aşama değer fonksiyonudur; x ve xi_s senaryosu verildiğinde başvuru eylemlerinin optimal maliyetidir. Birleşik program, senaryo sayısı arttıkça boyutu büyüyen büyük bir MIP'dir.
Formül
\min_{x \in X} c^T x + \mathbb{E}_\xi[Q(x,\xi)] \quad \text{s.t. } Ax = b,\; x \in \mathbb{Z}^p \times \mathbb{R}^{n-p}Ayrıştırma algoritmaları kullanarak çözün — dışbükey ikinci aşamalar için L-şekilli yöntem (Benders ayrıştırması), senaryo alt problemleriyle dal-kesme veya senaryo-paralel ayrıştırma için aşamalı koruma. İkinci aşamadaki tamsayılık ek kesmeler gerektirir (tamsayı L-şekilli kesmeler, kaldırma ve yansıtma). Modern çözücüler (CPLEX, geri çağrılarla Gurobi veya SMIP'e özgü kütüphaneler) bu rutinleri uygular.
Çözümü Stokastik Çözümün Değeri (VSS = EEV - RP) ve Mükemmel Bilginin Beklenen Değeri (EVPI = RP - WS) aracılığıyla değerlendirin; burada RP, başvuru probleminin optimal değeridir, EEV, deterministik ortalama değer çözümünü kullanmanın beklenen maliyetidir ve WS, bekle ve gör değeridir. Bu metrikler, belirsizliği açıkça modellemenin faydasını nicel olarak ifade eder.
Sık yapılan hatalar
- Çok az senaryo kullanmak belirsizliği eksik temsil eder ve aşırı güvenli çözümler üretir; çok fazla senaryo modeli hesaplama açısından imkansız hale getirir.
- İlk aşama ve ikinci aşama değişken rollerini karıştırmak, bilgi açıklanma zamanlamasına uymayan formülasyonlara yol açar.
- Beklenen değer çözümüne güvenmek (stokastikliği göz ardı etmek) önemli ölçüde suboptimal olabilir — SMIP çabasını haklı çıkarmak için her zaman VSS'yi hesaplayın.
- Başvuru aşamasında tamsayılık gerçekten mevcut olduğunda bunu ihmal etmek, çözümü pratikte uygulanamaz olabilecek bir gevşemeye yol açar.
- MIP için çözücü varsayılan ayarları, SMIP ayrıştırma çerçevelerinde genellikle ayar gerektirir (dallanma öncelikleri, kesme stratejileri).
Sık sorulan sorular
SMIP, normal Karma Tamsayılı Programlamadan nasıl farklıdır?
Normal MIP, sabit, bilinen parametreler altında optimize eder. SMIP, belirsiz parametreleri olasılıklarla bir senaryo kümesi olarak açıkça modeller, tüm senaryolarda beklenen performansı optimize ederken, ilk aşama kararlarının belirsizlik ortaya çıkmadan önce alınmasını sağlar.
Kaç senaryoya ihtiyacım var?
Evrensel bir kural yoktur. Bazı problemlerde 10-50 kadar az senaryo, kararlı ilk aşama kararları için yeterli olabilir; diğerleri binlerce gerektirebilir. Senaryo azaltma teknikleri ve kararlılık testleri (daha fazla senaryo ekledikçe optimal çözümün değişmediğini kontrol etmek) yeterliliği belirlemeye yardımcı olur.
L-şekilli yöntem nedir?
L-şekilli yöntem, stokastik programlar için uyarlanmış bir Benders ayrıştırmasıdır. İlk aşama değişkenleri ve senaryo alt problemleri üzerinde bir ana MIP'yi yinelemeli olarak çözer, yakınsayana kadar ana probleme optimallik ve fizibilite kesmeleri ekler. Tamsayı başvuru için, standart Benders kesmelerinin yerini tamsayı L-şekilli kesmeler alır.
L-şekilli yerine ne zaman aşamalı koruma kullanmalıyım?
Aşamalı koruma, alt problem yapısına göre değil, senaryoya göre ayrışır, bu da onu paralel hesaplama için çok uygun hale getirir. Senaryoların çok olduğu ve alt problemlerin büyük olduğu durumlarda ve algoritmanın bir küme üzerinde çalıştırılabildiği durumlarda tercih edilir. L-şekilli genellikle daha az, iyi yapılandırılmış senaryolar için tercih edilir.
SMIP iki aşamadan fazlasını ele alabilir mi?
Evet, ancak çok aşamalı SMIP, aşama sayısıyla üstel olarak büyüyen bir senaryo ağacı gerektirir ve ayrıştırma önemli ölçüde daha karmaşık hale gelir. Pratikte, çoğu uygulamalı SMIP modeli, çok dönemli dinamikleri yuvarlanan ufuk veya toplama yoluyla yaklaşık olarak temsil eden iki aşama kullanır.
İlgili yöntemler
Kaynaklar
Birge, J. R., & Louveaux, F. (1997). Introduction to Stochastic Programming. Springer Series in Operations Research. New York: Springer.
ISBN: 9780387982175Kopyalandı.Sen, S., & Higle, J. L. (2005). The C3 theorem and a D2 algorithm for large scale stochastic mixed-integer programming: Set convexification. Mathematical Programming, 104(1), 1–20.
DOI kaynağını açKopyalandı.