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

Karma Karışık Tamsayılı Programlama — Belirsizlik Altında Tamsayı Değişkenlerle Optimizasyon

Ortaya koyan
Ben-Tal & Nemirovski; Bertsimas & Sim
Yıl
1998–2004
Tür
Deterministic robust reformulation of MIP under uncertainty
Aile
Simulation / optimization

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

Yazı boyutu

Ne işe yarar?

Karma Karışık Tamsayılı Programlama (RMIP), belirsiz parametrelere rağmen geçerli ve tama yakın optimal çözümler bulmak için karmaşık tamsayılı programlamayı sağlam optimizasyon ile birleştirir.

Sabit veri varsaymak yerine, belirsizlik derecesini kontrol etmek için açık bir belirsizlik kümesi kullanarak, belirsiz girdilerin düşmanca veya en kötü durum gerçekleşmelerine karşı kararları korur, aynı zamanda tamsayı kararlarının kombinatoryal yapısını korur.

Yöntemin mantığı

Klasik karmaşık tamsayılı programlar tüm verilerin tam olarak bilindiğini varsayar, ancak pratikte maliyetler, talepler ve işlem süreleri dalgalanır. RMIP şunu sorar: belirsiz parametreler tanımlanmış bir aralıktaki en olası en kötü değerlerini aldığında hangi tamsayı ve sürekli kararlar en iyisidir? Belirsizliği doğrudan optimizasyon modeline gömerek, RMIP olasılıksal senaryolara başvurmadan veri varyasyonuna karşı bağışık planlar üretir. Bertsimas-Sim belirsizlik bütçesi yaklaşımı, uygulayıcıların tam sağlamlık ile ortalama durum verimliliği arasında seçim yapmalarını sağlar, koruma ve maliyet arasındaki değiş tokuşu açık hale getirir.

Tarih

Sürekli problemler için 1990'ların sonlarında Ben-Tal ve Nemirovski tarafından sağlam optimizasyon olarak çözülebilir bir paradigma kuruldu. Bertsimas ve Sim (2004), bunu belirsizlik bütçesi kümesiyle doğrusal programlara genişleterek doğrusal çözülebilirliği korudu. Sonraki çalışmalar bu çerçeveyi tamsayılı programlama ile entegre ederek, 2010'lar boyunca tedarik zinciri, enerji ve ulaşım araştırmalarında yaygın olarak benimsenen RMIP'yi ortaya çıkardı.

Ne zaman kullanılır?

Kararlar tamsayı veya ikili seçimler (tesis yeri, parti büyüklüğü, ağ tasarımı, çizelgeleme) içerdiğinde ve bazı girdi parametreleri belirsiz olduğunda ancak olasılık dağılımları mevcut olmadığında veya güvenilmez olduğunda RMIP kullanın. Kısıt ihlallerinin kabul edilemez olduğu (sert geçerlilik gereksinimleri) ve beklenen değer optimizasyonuna tercih edilen muhafazakar ancak deterministik bir garanti istendiğinde uygundur. Belirsizlik dağılımlarının iyi karakterize edildiği ve örnek-ortalama yaklaştırma veya stokastik MIP'nin mümkün olduğu durumlarda KULLANMAYIN; tüm karar değişkenlerinin sürekli olduğu durumlarda (bunun yerine sağlam LP kullanın); veya belirsizlik kümesinin ayrıştırma stratejileri olmadan modeli çözülemez hale getirecek kadar büyük olduğu durumlarda.

Sınırlar ve dikkat edilmesi gerekenler

  • Tasarım gereği muhafazakar — en kötü durum amaç fonksiyonu tipik olarak stokastik programlamanın beklenen durum amaç fonksiyonundan daha kötüdür.
  • Uygun bir belirsizlik kümesi seçimi alan bilgisi gerektirir; kötü seçilmiş bir küme aşırı korumaya veya yetersiz korumaya yol açar.
  • Sağlam yeniden formülasyonlar model boyutunu (ek değişkenler ve kısıtlar) önemli ölçüde artırabilir, bu da büyük örnekler için hesaplama yükünü artırır.
  • Çözüm performansıyla ilgili olasılık ifadeleri sağlamaz; olasılıksal risk ölçütleri gerektiğinde stokastik MIP daha uygundur.

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

Güçlü yönleri

  • Belirsiz parametreler için olasılık dağılımları gerektirmeden deterministik en kötü durum geçerlilik garantileri sağlar.
  • Belirsizlik bütçesi (Gamma) parametresi, sağlamlık ve optimallik arasındaki değiş tokuş üzerinde sezgisel, ayarlanabilir kontrol sağlar.
  • Yeniden formülasyon, MIP yapısını koruyarak olgun ticari çözücülerin ve dal-ve-kesme teknolojisinin kullanımına izin verir.
  • Ağ tasarımı, tesis yeri ve üretim çizelgeleme gibi zorlu kombinatoryal problemler için uygulanabilir.
  • Tam stokastik MIP'ye göre hesaplama açısından daha çözülebilir.

Uygulama alanları

  • Belirsiz talep ve teslim süreleri altında tedarik zinciri ağ tasarımı
  • Belirsiz yenilenebilir üretimle enerji sistemi kapasite artırımı planlaması
  • Hasta talebi belirsizliği altında sağlık tesisi yeri
  • Belirsiz uçuş gecikmeleriyle havayolu mürettebatı çizelgeleme
  • Belirsiz maliyetler ve işlem süreleri altında üretim parti büyüklüğü
  • Belirsiz trafik hacimleriyle telekomünikasyon ağı yönlendirme

Nasıl çalışır?

Nasıl çalışır?

1

Nominal MIP'yi formüle edin: karar değişkenlerini (ikili veya tamsayı y, sürekli x), amaç fonksiyonunu ve kısıtları belirleyin. Hangi parametrelerin (maliyet katsayıları, sağ taraf değerleri, teknoloji matrisi girdileri) belirsiz olduğunu ve korunması gerektiğini saptayın.

2

Belirsiz parametreler için bir U belirsizlik kümesi tanımlayın. Yaygın seçimler kutu kümeleri (her parametre için aralıklar), elipsoidal kümeler (korelasyonlu belirsizlik) veya Bertsimas-Sim bütçe kümesidir (en fazla Gamma parametresi aynı anda sapar), burada Gamma muhafazakarlığı kontrol eder.

3

Her belirsiz kısıtı, U'daki tüm gerçekleşmeler için geçerli olması gereken sağlam karşılığı ile değiştirin. Bütçe belirsizliği için bu, çözülebilir bir yeniden formülasyon sağlar: orijinal kısıt, sapmaların en kötü durum toplamını kontrol eden bir ceza terimi ile genişletilir. Sonuç, daha büyük ama yine de MIP çözülebilir bir modeldir.

4

Sağlam yeniden formüle edilmiş MIP'yi standart bir dal-ve-sınır veya dal-ve-kesme çözücüsü (örneğin, CPLEX, Gurobi, SCIP) ile çözün. Yeniden formülasyon, y üzerindeki bütünlük gereksinimlerini korur. Büyük ölçekli örnekler için Benders ayrıştırması veya kesme düzlemi yöntemleri problemi ayrıştırabilir.

5

Sağlam çözümü şu şekilde değerlendirin: (a) nominal ve en kötü durum parametreleri altında amaç değerini hesaplayın, (b) Monte Carlo senaryoları kullanarak stokastik programlama çözümüyle karşılaştırın ve (c) sağlamlığın fiyatını raporlayın — belirsizlik koruması için ödenen ek maliyet.

Sık yapılan hatalar

  • Gamma=0 (belirsizlik bütçesi yok) seçmek nominal MIP'yi tekrarlar ve hiçbir koruma sağlamaz; çok büyük Gamma aşırı muhafazakar, operasyonel olarak pratik olmayan çözümlere yol açar.
  • Tüm parametreleri aynı anda belirsiz olarak ele almak yeniden formülasyonu çözülemez hale getirebilir — seçici olarak korunacak kritik belirsiz parametreleri belirleyin.
  • Belirsizliklerin korelasyon yapısını göz ardı etmek aşırı karamsar bir belirsizlik kümesine yol açabilir; korelasyonlar biliniyorsa elipsoidal kümeler tercih edilir.
  • Yalnızca en kötü durum amacını nominal veya stokastik kıyaslamalarla karşılaştırmadan raporlamak, çözüm kalitesinin eksik bir resmini verir.

Sık sorulan sorular

RMIP, stokastik karmaşık tamsayılı programlamadan nasıl farklıdır?

Stokastik MIP, olasılık dağılımlarını kullanır ve örneklenmiş senaryolar üzerinden beklenen performansı optimize ederken, RMIP dağılımsal bilgi gerektirmeden bir belirsizlik kümesi içindeki en kötü duruma karşı korur. RMIP tek bir deterministik sağlam çözüm sunar; stokastik MIP ortalamada iyi olan bir politika sunar.

Sağlamlığın fiyatı nedir ve tipik olarak ne kadardır?

Sağlamlığın fiyatı, amaç fonksiyonu değerinin nominal (belirsizlik yok) optimuma kıyasla yüzdelik artışıdır. Bertsimas ve Sim, bunun Gamma ile yaklaşık olarak doğrusal büyüdüğünü, ancak tipik bütçe değerleri için mütevazı kaldığını, pratik uygulamalarda genellikle %5-15 olduğunu göstermektedir.

RMIP, belirsiz sağ taraf değerlerini ve belirsiz maliyet katsayılarını aynı şekilde ele alabilir mi?

Evet. Kısıt sağ taraflarındaki belirsizlik sağlam geçerlilik kısıtlarına yol açarken, amaç katsayılarındaki belirsizlik sağlam optimalliği etkiler. Her ikisi de belirsizlik bütçesi çerçevesi içinde aynı anda ele alınabilir, ancak yeniden formülasyon yapısı farklıdır.

RMIP standart MIP çözücüleri ile çözülebilir mi?

Bertsimas-Sim bütçe kümesi için, sağlam yeniden formülasyon bir MIP olarak kalır ve CPLEX veya Gurobi gibi çözücülerle doğrudan çözülebilir. Elipsoidal belirsizlik kümeleri, modern çözücüler tarafından da desteklenen karışık tamsayılı ikinci dereceden koni programları (MISOCP) üretir.

Kutu belirsizlik kümesi yerine neden bütçe-belirsizlik kümesini tercih etmeliyim?

Bir kutu kümesi, tüm parametrelerin aynı anda aşırı değerlerine sapmasına karşı koruma sağlar, bu genellikle aşırı muhafazakardır. Bütçe kümesi (Gamma), tüm parametrelerin eşzamanlı en kötü durum sapmalarının olası olmadığı durumlarda tercih edilir, çünkü daha az muhafazakar ve daha uygun maliyetli çözümler sunar.

İlgili yöntemler

Kaynaklar

  1. Bertsimas, D., Sim, M. (2004). The price of robustness. Operations Research, 52(1), 35–53.

    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ı.