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

Belirsizlik Altında Sağlam Doğrusal Programlama — Optimizasyon

Ortaya koyan
Ben-Tal, A. and Nemirovski, A.; further developed by Bertsimas, D. and Sim, M.
Yıl
1999–2004
Tür
Uncertainty-robust linear optimization
Aile
Simulation / optimization

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

Yazı boyutu

Ne işe yarar?

Sağlam Doğrusal Programlama (SDP), problem verilerindeki — maliyet katsayıları, kısıt katsayıları veya sağ taraf değerlerindeki — belirsizliği, tanımlanmış bir belirsizlik kümesi içindeki belirsiz parametrelerin tüm gerçekleşmeleri boyunca çözümlerin geçerli ve optimuma yakın kalmasını gerektirerek ele almak üzere klasik doğrusal programlamayı genişletir.

Dağılımsal bilginin sınırlı olduğu durumlarda pratik hale getiren, olasılıksal varsayımları en kötü durum garantileriyle değiştirir.

Yöntemin mantığı

Sıradan doğrusal programlama, tüm verilerin kesin olarak bilindiği varsayımıyla en iyi çözümü bulur. Pratikte, katsayılar hata ile tahmin edilir, öngörülür veya ölçülür. SDP, şu soruyu sorar: belirsiz parametreler makul bir aralıkta nasıl değişirse değişsin geçerli kalan en iyi karar nedir? Analist bir belirsizlik kümesi — bir kutu, elipsoid veya polihedral bölge — belirtir ve çözücü bu küme içindeki en kötü durum için optimum olan planı bulur. Bertsimas ve Sim'in belirsizlik bütçesi formülasyonu, analistin muhafazakarlığı ayarlamasına olanak tanır: bir Gama parametresi, kaç katsayının eş zamanlı olarak sapmasına izin verildiğini kontrol eder, nominal Doğrusal Programlama ile tamamen muhafazakar en kötü durum arasında enterpolasyon yapar.

Tarih

Sağlam optimizasyon, belirsiz doğrusal programların elipsoidal belirsizlik kümeleriyle çözülebilir ikinci dereceden koni programları verdiğini gösteren Ben-Tal ve Nemirovski (1999) tarafından sağlam bir teorik temele oturtulmuştur. Bertsimas ve Sim (2004), yeniden formülasyonu doğrusal program olarak tutan ve tek bir parametre aracılığıyla sağlamlığı ayarlanabilir hale getiren belirsizlik bütçesi çerçevesini tanıttı ve bu da operasyon araştırmaları ve mühendislik alanlarında pratik benimsenmesini büyük ölçüde genişletti.

Ne zaman kullanılır?

Veri belirsizliğinin gerçek olduğu ancak olasılık dağılımlarının bilinmediği veya güvenilmez olduğu durumlarda SDP'yi kullanın; örneğin, belirsiz talep ile tedarik zinciri planlaması, tahmin hataları ile enerji sevkiyatı veya belirsiz getirilerle finansal portföy oluşturma gibi. Kısıt geçerliliğinin tüm senaryolarda müzakere edilemez olduğu durumlarda uygundur. Belirsizliğin amaç fonksiyonu ölçeğine göre ihmal edilebilir olduğu, olasılık dağılımlarının iyi karakterize edildiği (stokastik programlama tercih edilebilir), belirsiz parametre sayısının sağlam karşılığın çözülemez hale geleceği kadar büyük olduğu veya en kötü durum senaryosunun uygulama için gerçekçi olmayan şekilde karamsar olduğu durumlarda SDP'den kaçının.

Sınırlar ve dikkat edilmesi gerekenler

  • En kötü durum yönelimi, aşırı senaryoların son derece olasılık dışı olduğu durumlarda aşırı muhafazakar çözümler üretebilir.
  • Elipsoidal belirsizlik kümeleri, çözülebilir ikinci dereceden koni programları verir ancak artık saf Doğrusal Programlamalar değildir, bu da çözücü gereksinimlerini artırır.
  • Analistin, sonuçları önemli ölçüde etkileyen bir modelleme seçimi olan bir belirsizlik kümesi belirtmesini gerektirir.
  • Doğrudan ihlal olasılığı ifadeleri sağlamaz; kuyruk olasılıkları önemliyse stokastik programlama daha iyidir.
  • Gama = 0 olduğunda nominal Doğrusal Programlamaya indirgenir, belirsizliğe karşı hiçbir koruma sağlamaz.

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

Güçlü yönleri

  • Dağılımsal varsayımlar gerektirmeden kesin en kötü durum geçerlilik garantileri sağlar.
  • Bertsimas-Sim bütçe formülasyonu, hazır çözücülerle çözülebilen çözülebilir bir Doğrusal Programlama karşılığı üretir.
  • Sağlamlık bütçesi Gama, analiste çözüm kalitesi ile muhafazakarlık arasında bir denge kurmak için sezgisel bir ayar sunar.
  • Hesaplama açısından verimli — bütçe kümeleri için sağlam karşılıklar, orijinal Doğrusal Programlama ile benzer karmaşıklığa sahiptir.
  • Özellikle kısıt ihlalinin maliyetli veya güvensiz olduğu problemler için çok uygundur.

Uygulama alanları

  • Belirsiz nakliye maliyetleri ve talebi ile tedarik zinciri ağı tasarımı
  • Yenilenebilir enerji tahmini belirsizliği altında elektrik gücü sistemi sevkiyatı
  • Belirsiz varlık getirisi aralıklarıyla portföy optimizasyonu
  • Hasta hareketi belirsizliği ile radyasyon tedavisi planlaması
  • Belirsiz uçuş gecikmeleri ile havayolu mürettebatı çizelgelemesi
  • Belirsiz yağış ve buharlaşma ile su kaynakları tahsisi

Nasıl çalışır?

Nasıl çalışır?

1

Nominal doğrusal programı formüle edin: doğrusal eşitsizlik kısıtları Ax <= b ve negatif olmama koşulları altında doğrusal bir amaç fonksiyonunu c^T x minimize edin. Hangi katsayıların — tipik olarak kısıt matrisi girdileri a_ij — belirsiz olduğunu belirleyin. Bu adım standart Doğrusal Programlama modellemesini yansıtır ancak her belirsiz parametreyi işaretler.

Formül
\min c^T x \text{ s.t. } Ax \leq b, \; x \geq 0
2

Olasılık dağılımı gerektirmeyen makul parametre değerleri aralığını yakalayan bir belirsizlik kümesi U oluşturun. Yaygın seçimler kutu kümeleri (her parametre [a_bar - a_hat, a_bar + a_hat] içinde bağımsız olarak değişir), elipsoidal kümeler (Ben-Tal ve Nemirovski, 1999) ve bütçe kümeleridir (Bertsimas ve Sim, 2004). Gama bütçe parametresi, kaç parametrenin eş zamanlı olarak en kötü durum değerlerini alabileceğini sınırlar.

Formül
\mathcal{U} = \{ a_i : a_i = \bar{a}_i + \hat{a}_i \xi_i, \; \|\xi\|_\infty \leq 1 \}
3

Her belirsiz kısıtı sağlam karşılığıyla değiştirin: U içindeki her gerçekleşme için geçerliliği gerektirin. Bu, orijinal problemi yarı-sonsuz bir programa dönüştürür — sonsuz sayıda kısıt, her biri U'nun bir elemanı için.

Formül
\max_{a_i \in \mathcal{U}} a_i^T x \leq b_i \quad \forall i
4

Çözülebilir deterministik bir eşdeğer türetin. Bütçe belirsizlik kümeleri için sağlam karşılık, standart bir Doğrusal Programlama veya benzer boyutta karışık-tam sayılı Doğrusal Programlama olarak yeniden formüle edilir ve geleneksel çözücülerle çözülebilir. Anahtar yeniden formülasyon, belirsizlik kümesi üzerindeki iç maksimizasyonu doğrusallaştıran yardımcı değişkenler tanıtır.

Formül
\bar{a}_i^T x + \Gamma_i \max_{\{S: |S| \leq \Gamma_i\}} \sum_{j \in S} \hat{a}_{ij} |x_j| \leq b_i
5

Yeniden formüle edilmiş Doğrusal Programlamayı standart bir çözücü (simpleks veya iç nokta) kullanarak çözün. Çözümü değerlendirin: belirsizlik kümesi boyunca en kötü durum kısıt ihlalini kontrol edin, sağlamlık maliyetini (nominal Doğrusal Programlamaya göre amaç fonksiyonundaki artış) raporlayın ve sağlamlık bütçesi Gama üzerinde hassasiyet analizi yapın.

Sık yapılan hatalar

  • Gama'yı çok yüksek ayarlamak, her kısıtın eş zamanlı olarak en kötü durumda olmasına neden olur, bu da aşırı muhafazakar ve pahalı bir çözüme yol açar.
  • Belirsizlik kümesinin yanlış belirtilmesi (örneğin, korelasyon yapısının göz ardı edilmesi) aşırı veya yetersiz korumaya yol açabilir.
  • Sağlam Doğrusal Programlamayı stokastik Doğrusal Programlama ile karıştırmak: SDP en kötü durum performansını maksimize eder, beklenen performansı değil.
  • Sağlamlık maliyeti raporunu göz ardı etmek — muhafazakarlık maliyetini ölçmek için her zaman sağlam çözümün amaç fonksiyonunu nominal Doğrusal Programlama çözümüyle karşılaştırın.
  • Tamsayılı değişkenleri olan problemlere, farklı yeniden formülasyonlar gerektiren sağlam karışık-tamsayılı formülasyona geçmeden uygulamak.

Sık sorulan sorular

Sağlam Doğrusal Programlama Stokastik Doğrusal Programlamadan Nasıl Farklıdır?

Stokastik Doğrusal Programlama, olasılık dağılımı verildiğinde beklenen performansı senaryolar üzerinden optimize eder ve dağılımsal bilgi gerektirir. Sağlam Doğrusal Programlama, belirsizlik kümesi üzerinden en kötü durum performansını optimize eder ve yalnızca sınırlar gerektirir — olasılık dağılımı gerekmez. Dağılımlar güvenilmez olduğunda Sağlam Doğrusal Programlama tercih edilir; iyi tahmin edildiklerinde stokastik Doğrusal Programlama tercih edilir.

Sağlamlık maliyeti nedir?

Sağlamlık maliyeti, sağlam çözümün amaç fonksiyonu değerindeki (maliyet) nominal Doğrusal Programlama çözümüne göre artıştır. Bertsimas ve Sim (2004), bu maliyetin bütçe kümeleri için belirsiz parametre sayısının karekökü kadar arttığını kanıtlamıştır, bu da sağlamlığı şaşırtıcı derecede uygun fiyatlı hale getirir.

Sağlamlık bütçesi Gama nedir?

Gama, Bertsimas-Sim modelinde, kaç belirsiz katsayının eş zamanlı olarak en kötü durum değerlerini almasına izin verildiğini kontrol eden bir parametredir. Gama = 0 nominal Doğrusal Programlamayı geri getirir; Gama = n, tüm n parametresinin aynı anda sapmasına karşı koruma sağlar. Analistler tipik olarak Gama'yı kabul edilebilir ihlal olasılığı sınırlarına göre seçerler.

Sağlam Doğrusal Programlama özel bir çözücü gerektirir mi?

Hayır. Kutu ve bütçe belirsizlik kümeleri için sağlam karşılık, kendisi bir doğrusal programdır ve herhangi bir standart Doğrusal Programlama çözücüsü (CPLEX, Gurobi, HiGHS vb.) ile çözülebilir. Elipsoidal kümeler, yaygın olarak desteklenen ikinci dereceden koni programı çözücüsü gerektirir.

Ne zaman Sağlam Karışık-Tamsayılı Programlama kullanmalıyım?

Karar değişkenleri tamsayılı olmak zorundaysa (örneğin, ikili evet/hayır kararları, parti boyutları), sağlam karşılık tamsayılı değişkenler içerir ve Sağlam Karışık-Tamsayılı Programlama haline gelir. Belirsizlik kümesi yaklaşımı aynıdır, ancak yeniden formülasyon ve çözücü gereksinimleri buna göre değişir.

İ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., Nemirovski, A. (1999). Robust solutions of uncertain linear programs. Operations Research Letters, 25(1), 1–13.

    DOI kaynağını aç
    Kopyalandı.