İçeriğe atla
Arama sonuçlarına dön

Sağlam Tamsayı Programlama — Belirsizlik Altında Bütünlük Kısıtlamalarıyla Optimizasyon

Ortaya koyan
Bertsimas, D. and Sim, M.
Yıl
2003
Tür
Deterministic robust optimization with integer variables
Aile
Simulation / optimization

Bu metin makine çevirisidir ve henüz incelenmedi. Asıl metni İngilizce oku

Yazı boyutu

Ne işe yarar?

Sağlam Tamsayı Programlama (RIP), belirlenmiş bir belirsizlik kümesindeki tüm senaryolar boyunca geçerli ve tama yakın optimal kalan tamsayı veya ikili çözümler bulur.

Verilere tam olarak hakim olunduğu varsayımı yerine, RIP belirsiz maliyetlerin veya kısıt katsayılarının en kötü durum gerçekleşmesine karşı korunma sağlar ve girdiler nominal değerlerinden saptığında bile iyi performans gösterecek kararlar sunar.

Yöntemin mantığı

Gerçek dünyadaki birçok karar — üretim çizelgeleri, ağ tasarımı, kaynak tahsisi — tamsayılar (yarım birim üretemezsiniz veya yarım tesis inşa edemezsiniz) ve belirsiz veriler (maliyetler, talepler, seyahat süreleri dalgalanır) içerir. Klasik tamsayı programlama belirsizliği göz ardı eder ve girdiler tahminlerden farklı olduğunda kötü sonuç verebilecek çözümler üretebilir. Sağlam tamsayı programlama, belirsizliği açıkça bir belirsizlik kümesi aracılığıyla modeller ve en kötü durumda en iyi performansı gösteren tamsayı çözümünü bulur. Bertsimas-Sim yaklaşımı, muhafazakarlığı kontrol etmek için bir belirsizlik bütçesi parametresi kullanır: sıfır bütçe ile problem deterministik IP'ye indirgenir; bütçe büyüdükçe, çözümler veri pertürbasyonlarına karşı giderek daha fazla korunur, ancak bu durum hedef değer pahasına gerçekleşir.

Tarih

Sağlam ayrık optimizasyonun sistematik çalışması, Bertsimas ve Sim tarafından 2003 tarihli makalelerinde ayrık problemler için belirsizlik bütçesi modeli tanıtılarak, Ben-Tal ve Nemirovski (1998) ve El Ghaoui ve Lebret (1997) tarafından yapılan önceki sağlam LP çalışmalarına dayanarak ilerletilmiştir. Bertsimas ve Sim, bütçe belirsizliği altındaki tamsayı programlarının sağlam karşılıklarının izlenebilir MIP'ler olarak kaldığını göstererek, lojistik, ağ tasarımı ve çizelgeleme alanlarında kapsamlı uygulamaları teşvik etti. Ben-Tal, El Ghaoui ve Nemirovski'nin 2009 tarihli monografisi, sürekli ve ayrık ortamlarda sağlam optimizasyonun teorik temellerini pekiştirdi.

Ne zaman kullanılır?

Kararların ayrık seçimler (ikili atama, ağ tasarımı, çizelgeleme, parti büyüklüğü) içerdiği ve girdi verilerinin belirsiz ancak bilinen bir kümede sınırlı olduğu durumlarda Sağlam Tamsayı Programlamayı kullanın. Belirsizliğin olasılık dağılımı bilinmediğinde veya güvenilmez olduğunda ve en kötü durum garantisi gerektiğinde stokastik tamsayı programlamaya tercih edilir. Belirsizlik yalnızca stokastik ve iyi tahmin edilmiş dağılımlara sahip olduğunda (bunun yerine stokastik programlama kullanın), problem tamamen sürekli olduğunda (sağlam doğrusal programlama kullanın), belirsizlik kümesi çok muhafazakar olduğunda ve sağlamlığın bedeli kabul edilemez olduğunda veya problem boyutu nominal tamsayı programlamayı bile çözülemez hale getirdiğinde RİP KULLANMAYIN.

Sınırlar ve dikkat edilmesi gerekenler

  • En kötü durum yönelimi aşırı muhafazakar olabilir ve düşmanca senaryolar olası olmadığında bile deterministik optimalden önemli ölçüde daha yüksek hedef değerlere sahip çözümler üretebilir.
  • İzlenebilirlik, belirsizlik kümesinin seçimine bağlıdır; genel dışbükey veya dışbükey olmayan kümeler sağlam karşılığı hesaplama açısından zor hale getirebilir.
  • Olasılık bilgisini doğal olarak dahil etmez; nadir ama yüksek etkili olaylar, olası pertürbasyonlarla aynı muameleyi görür.
  • Büyük ölçekli sağlam tamsayı programları, özellikle çok sayıda belirsiz parametre içeren problemler için hala hesaplama açısından pahalı olabilir.
  • Uygun belirsizlik kümesinin ve bütçe seviyesinin seçilmesi alan uzmanlığı gerektirir ve sonuçları önemli ölçüde etkileyebilir.

Kaynak metnin koşulları, bağımsız bilimsel inceleme veya analiz motoru doğrulaması yerine geçmez.

Güçlü yönleri

  • Belirsiz parametrelerin olasılık dağılımını bilmeye gerek kalmadan deterministik en kötü durum garantileri sağlar.
  • Bertsimas-Sim belirsizlik bütçesi çerçevesi, sağlam karşılığın izlenebilir kalmasını sağlar — genellikle nominal probleme benzer boyutta standart bir MIP.
  • Muhafazakarlık seviyesi, tek bir bütçe parametresi Gamma aracılığıyla kolayca kontrol edilir, bu da koruma ve maliyet arasında açık değiş tokuş analizi sağlar.
  • Lojistik, enerji, finans, telekomünikasyon, çizelgeleme gibi çok çeşitli alanlarda uygulanabilir.
  • En kötü durum senaryosu sınırlı ve doğrulanabilir olduğundan çözümler pratikte uygulanabilir.

Uygulama alanları

  • Belirsiz talepler veya seyahat süreleri altında sağlam tesis yeri ve ağ tasarımı
  • Belirsiz işlem süreleri veya verim oranları ile parti büyüklüğü ve üretim çizelgeleme
  • Kardinalite kısıtlamaları ve belirsiz varlık getirileri ile portföy optimizasyonu
  • Belirsiz afet parametreleri altında acil durum müdahalesi ve insani yardım lojistiği
  • Belirsiz yenilenebilir çıktı ile enerji sistemi planlaması (birim taahhüdü, üretim genişletme)
  • Belirsiz trafik talepleri altında telekomünikasyon ağı yönlendirmesi

Nasıl çalışır?

Nasıl çalışır?

1

Belirsiz parametrelere sahip tamsayı programını formüle edin: belirsizlik kümesindeki tüm gerçekleşmeler için geçerli olması gereken kısıtlamalara tabi olarak, en kötü durum hedefinin minimize edilmesi (veya maksimize edilmesi). Karar değişkenleri x tamsayı veya ikili olmalı ve problem, en kötü durum senaryosunu seçen iç problemle min-max (veya max-min) çift seviyeli bir yapı olarak kurulur.

Formül
\min_{x \in \mathcal{X}} \max_{\xi \in \mathcal{U}} c(\xi)^\top x \quad \text{s.t.} \quad A(\xi)x \leq b,\; x \in \mathbb{Z}^n
2

Parametre varyasyonunun olası aralığını yakalayan bir belirsizlik kümesi U tanımlayın. Yaygın seçimler arasında kutu kümeleri (her parametre için bağımsız aralık sınırları), elipsoidal kümeler (korelasyonlu belirsizlik) ve en fazla Gamma parametresinin nominal değerlerinden eş zamanlı olarak saptığı Bertsimas-Sim belirsizlik bütçesi kümesi bulunur. Gamma bütçesi temel muhafazakarlık kaldıraçıdır.

Formül
\mathcal{U} = \{\xi : \|\xi - \hat{\xi}\|_\infty \leq \Gamma\} \quad (\text{budget-of-uncertainty, Bertsimas-Sim})
3

İç en kötü durum maksimizasyonunu ikili hale getirin veya yeniden formüle ederek tek seviyeli karışık tamsayı programı elde edin. Belirsizlik bütçesi modeli altında, sağlam karşılık yardımcı sürekli değişkenler ve doğrusal kısıtlamalar getirir, standart dal-ve-kesme veya dal-ve-kesme çözücülerinin izlenebilirliğini üstel senaryo sayımı olmadan korur.

4

Formüle edilmiş sağlam tamsayı programını standart bir MIP çözücüsü (CPLEX, Gurobi, SCIP) veya özel dal-ve-kesme ile sağlam sınırlama prosedürleri kullanarak çözün. Büyük örnekler için, ana tamsayı problemini düşmanca alt problemden ayırmak üzere Benders ayrıştırması veya sütun-ve-kısıtlama üretimi gibi ayrıştırma yöntemleri uygulanabilir.

5

Sağlam çözümü deterministik optimal ve örnek dışı senaryo kümesine karşı değerlendirin. Sağlamlığın bedelini (sağlam ve nominal çözümler arasındaki hedef boşluğu) raporlayın ve sağlam çözümün en kötü durum senaryosu altında tüm kısıtlamaları karşıladığını doğrulayın. Gamma üzerinden duyarlılık analizi, uygulayıcıya koruma seviyesi ile çözüm maliyeti arasındaki değiş tokuşu yönlendirir.

Sık yapılan hatalar

  • Belirsizlik bütçesi Gamma'yı çok yüksek ayarlamak aşırı muhafazakar, pratikte kullanışsız çözümler üretir; Gamma'yı geçmiş sapma sıklığına göre kalibre etmek önerilir.
  • Sağlam karşılık yeniden formülasyonunun seçilen belirsizlik kümesi için geçerli olduğunu doğrulama hatası — bazı yeniden formülasyonlar yalnızca belirli küme türleri için geçerlidir (örneğin, elipsoidal kümeler değil, bütçe kümeleri).
  • Sağlam tamsayı programlamayı stokastik tamsayı programlamayla karıştırmak: RIP beklenen değeri optimize etmez ve senaryo ağacı veya olasılık dağılımı gerektirmez.
  • Sağlamlığın bedeli analizini göz ardı etmek — uygulayıcılar, korumanın maliyete değip değmediğini değerlendirmek için her zaman sağlam ve nominal hedef değerlerini karşılaştırmalıdır.
  • Belirsizliğin sağ tarafı doğrusal olmayan şekilde etkilediği problemlere, sonuçta ortaya çıkan alt problemin izlenebilir kaldığını doğrulamadan RIP uygulamak.

Sık sorulan sorular

Sağlam Tamsayı Programlama, Stokastik Tamsayı Programlamadan nasıl farklıdır?

Stokastik tamsayı programlama, senaryoların olasılık dağılımı üzerinden beklenen performansı optimize eder ve tipik olarak senaryo ağaçları gerektirir. Sağlam tamsayı programlama, belirsizlik kümesi üzerinden en kötü durum performansını optimize eder ve olasılık dağılımı gerektirmez — yalnızca belirsizlik sınırları gerektirir. RIP, sert geçerlilik garantileri verir; stokastik IP, olasılıksal garantiler verir.

Belirsizlik bütçesi nedir ve onu nasıl seçerim?

Gamma bütçesi, kaç belirsiz parametrenin eş zamanlı olarak nominal değerlerinden saptığını sınırlar. Gamma sıfıra eşit olduğunda, model deterministik IP'ye indirgenir. Gamma arttıkça, çözümler daha sağlam ama daha maliyetli hale gelir. Pratik bir kural, Gamma'yı geçmiş verilere göre ayarlamaktır: bir zaman penceresinde tipik olarak en fazla k parametre saparsa, Gamma'yı k olarak ayarlayın. Alternatif olarak, Bertsimas ve Sim, belirli bir Gamma için kısıtlama ihlaline ilişkin olasılıksal sınırlar sağlar.

Bir tamsayı programının sağlam karşılığı hala bir tamsayı programı mıdır?

Evet. Belirsizlik bütçesi modeli altında, sağlam karşılık ek sürekli yardımcı değişkenler ve doğrusal kısıtlamalar getirir ancak orijinal karar değişkenlerinin bütünlüğünü korur. Sonuç, standart MIP çözücülerle çözülebilen standart bir MIP'dir.

Sağlam Tamsayı Programlama ne zaman hesaplama açısından izlenebilirdir?

İkili problemleri kapalı formda veya LP ile temsil edilebilir çözümlere sahip olan belirsizlik kümeleri için izlenebilirlik geçerlidir, örneğin kutu kümeleri, bütçe kümeleri ve polihedral kümeler. Tamsayı programlarındaki elipsoidal belirsizlik, genellikle daha zor olan ikinci dereceden koni kısıtlamalarına yol açar. Çok sayıda tamsayı değişkeni ve büyük belirsizlik kümeleri içeren problemler hala ayrıştırma yöntemleri gerektirebilir.

Sağlam Tamsayı Programlama çoklu hedefleri işleyebilir mi?

Evet, her hedef sağlam bir şekilde ele alındığı Sağlam Çok Amaçlı Tamsayı Programlamaya genişletilerek. Bu, sağlam Pareto sınırlarına yol açar. Alternatif olarak, uygulayıcılar hedefleri ölçeklendirir (ağırlıklı toplam veya epsilon-kısıtlama) ve sonuçta ortaya çıkan tek amaçlı probleme standart RIP uygular.

İlgili yöntemler

Kaynaklar

  1. Bertsimas, D., Sim, M. (2003). Robust discrete optimization and network flows. Mathematical Programming, 98(1-3), 49-71.

    DOI kaynağını aç
    Kopyalandı.
  2. Ben-Tal, A., El Ghaoui, L., Nemirovski, A. (2009). Robust Optimization. Princeton University Press, Princeton, NJ.

    ISBN: 9780691143682
    Kopyalandı.