Çok Amaçlı Karma Tamsayılı Programlama
- Ortaya koyan
- Ehrgott, M.; Mavrotas, G. and others in multi-criteria optimization
- Yıl
- 1980s–2000s
- Tür
- Mathematical optimization
- Aile
- Simulation / optimization
Bu metin makine çevirisidir ve henüz incelenmedi. Asıl metni İngilizce oku
Ne işe yarar?
Çok Amaçlı Karma Tamsayılı Programlama (MO-MIP), doğrusal veya doğrusal olmayan kısıtlamalara tabi olarak, iki veya daha fazla çelişen amaç fonksiyonunu eş zamanlı olarak optimize eden ve karar değişkenlerinin bazılarının tamsayı değerlere kısıtlandığı, diğerlerinin ise sürekli olduğu bir optimizasyon çerçevesidir.
Mühendislik tasarımı, tedarik zinciri planlaması, kaynak tahsisi ve ayrık seçimleri sürekli miktarlarla birlikte gerektiren zamanlama problemlerinde yaygın olarak uygulanır.
Yöntemin mantığı
Gerçek dünya kararlarının çoğu hem ayrık seçimleri (kaç tesis açılacağı, hangi projelere fon sağlanacağı, bir makine alınıp alınmayacağı) hem de sürekli kararları (ne kadar üretileceği, bir bütçenin nasıl tahsis edileceği) içerir. Bu seçimler aynı anda birden fazla çelişen hedefi etkilediğinde - örneğin, hizmet düzeyini en üst düzeye çıkarırken maliyeti en aza indirmek - tek bir optimal çözüm mevcut değildir. Bunun yerine, MO-MIP, tek bir zorunlu cevap yerine, uygulanabilir uzlaşmaların yapılandırılmış bir haritasını sunarak, baskın olmayan tüm çözümlerin takas sınırını (Pareto cephesini) araştırır.
Tarih
Karma tamsayılı programlama, 1950'ler-1960'larda Gomory ve Land ile Doig'in çalışmalarıyla biçimlendi. Mühendislik ve operasyon araştırması problemlerinin çoğunun rekabetçi hedefler içerdiği fark edildiğinde, çok amaçlı uzantılar 1970'ler-1980'lerde ortaya çıktı. Sistematik tedavi, Ehrgott (2005) ve Mavrotas (2009) tarafından pekiştirildi; bunların epsilon-kısıtlama uygulaması, pratik MO-MIP için yaygın olarak atıfta bulunulan bir referans olmaya devam etmektedir.
Ne zaman kullanılır?
Karar problemi doğal olarak sürekli miktarların yanı sıra tamsayı veya ikili değişkenler (tesis konumu, proje seçimi, zamanlama) içerdiğinde ve iki veya daha fazla çelişen amacın açıkça dengelenmesi gerektiğinde MO-MIP kullanın. Kesin veya tama yakın Pareto çözümlerinin gerekli olduğu ve hesaplama kaynaklarının dal-sınır aramasına izin verdiği durumlarda uygundur. Tüm değişkenlerin sürekli olduğu (bunun yerine çok amaçlı LP veya doğrusal olmayan programlama kullanın), problem ölçeğinin kesin MIP çözümünü çözülemez hale getirdiği ve meta-sezgisellerin daha pratik olduğu veya tek bir toplu amacın yeterli olduğu ve çok amaçlı analizin karar değeri katmadığı durumlarda KULLANMAYIN.
Sınırlar ve dikkat edilmesi gerekenler
- Hesaplama maliyeti, tamsayı değişkenlerinin sayısı ve problem boyutuyla üstel olarak artar; büyük örnekler kesin yöntemler için çözülemez olabilir.
- Tüm amaçların ve kısıtlamaların matematiksel biçimde kesin formülasyonunu gerektirir, bu da nitel veya belirsiz gerçek dünya hedefleri için zor olabilir.
- Ağırlıklı toplam gibi skalerleştirme yöntemleri, Pareto cephesinin dışbükey olmayan bölgelerindeki çözümleri keşfedemez, bu da potansiyel olarak önemli takasları kaçırır.
- Yoğun bir Pareto cephesi oluşturmak, birçok MIP alt probleminin çözülmesini gerektirir, bu da toplam hesaplama süresini katlar.
- Sonuçlar, kısıtlama formülasyonuna ve problem verilerinin doğruluğuna duyarlıdır; uygun olmayan veya kötü sınırlanmış modeller faydalı bir çıktı vermez.
Kaynak metnin koşulları, bağımsız bilimsel inceleme veya analiz motoru doğrulaması yerine geçmez.
Güçlü yönleri
- İşlenebilir problem boyutları için Pareto cephesi kalitesini garanti eden, her skalerleştirilmiş alt problem için kanıtlanabilir şekilde optimal veya tama yakın çözümler sağlar.
- Sürekli gevşetmelerin doğru bir şekilde temsil edemeyeceği gerçek dünya ayrık seçimlerini (ikili kararlar, tamsayı miktarları) doğal olarak ele alır.
- Tek bir zorunlu uzlaşma yerine karar vericilere şeffaf, yapılandırılmış takas bilgileri veren tam bir Pareto cephesi verir.
- Epsilon-kısıtlama ve diğer sistematik skalerleştirmeler, baskın olmayan çözüm kümesinin kontrollü, yoğun bir şekilde araştırılmasını sağlar.
- Büyük ölçekli MIP problemlerini işleyen çok çeşitli ticari ve açık kaynaklı çözümleyicilerle (CPLEX, Gurobi, GLPK, CBC) uyumludur.
Uygulama alanları
- Tesis konumu ve tedarik zinciri ağ tasarımı: ikili açık/kapalı değişkenlerle maliyeti en aza indirme ve müşteri hizmeti kapsamını en üst düzeye çıkarma.
- Sermaye bütçelemesi ve proje portföy seçimi: ikili proje seçimi değişkenleriyle bütçe ve kaynak kısıtlamalarına tabi olarak getiriyi en üst düzeye çıkarma ve riski en aza indirme.
- Üretim zamanlaması: tamsayı parti boyutları ve ikili makine atamalarıyla bitirme süresini ve gecikmeyi eş zamanlı olarak en aza indirme.
- Enerji sistemi planlaması: ayrık yatırım kararları ve sürekli sevk değişkenleriyle güç santrali karışımı için maliyeti ve CO2 emisyonlarını optimize etme.
- Sağlık hizmeti kaynak tahsisi: tamsayı personel ve ikili tesis kararlarını kullanarak hasta kapsamını ve eşitliğini en üst düzeye çıkarma ve harcamaları en aza indirme.
- Ulaşım ve lojistik: ikili araç filosu ve rota kararlarıyla seyahat süresini ve emisyonları eş zamanlı olarak en aza indirme.
Nasıl çalışır?
Nasıl çalışır?
en aza indirilecek veya en üst düzeye çıkarılacak k amaç fonksiyonunu f_1(x), ..., f_k(x), bir dizi doğrusal veya doğrusal olmayan kısıtlamayı Ax <= b ve bazı değişkenlerin tamsayı değerli (örneğin, ikili 0/1) diğerlerinin ise sürekli olduğu değişken alanlarını belirleyerek problemi formüle edin. Çözmeden önce sınırları ve verileri net bir şekilde tanımlayın.
Çok amaçlı problemi tek amaçlı MIP alt problemler dizisine dönüştürmek için bir skalerleştirme veya ayrıştırma stratejisi uygulayın. Yaygın stratejiler arasında ağırlıklı toplam yöntemi (w_i * f_i toplamını en aza indirme), epsilon-kısıtlama yöntemi (diğerlerini eşik seviyelerine sınırlarken bir amacı optimize etme) ve başarı skalerleştirme fonksiyonları bulunur.
Her skalerleştirilmiş MIP alt problemini bir dal-sınır, dal-kesme veya başka bir kesin çözümleyici (örneğin, CPLEX, Gurobi, GLPK) kullanarak çözün. Her alt problem için çözümleyici, her düğümde LP gevşetmelerini uygulayarak ve uygun olmayan veya baskın dalları budayarak tamsayı-uygun çözüm alanını araştırır.
Pareto cephesini yaklaştırmak veya tam olarak oluşturmak için alt problem çalıştırmaları boyunca baskın olmayan tüm çözümleri toplayın. İki çözüm, her ikisi de diğerinden tüm amaçlar açısından kesin olarak daha iyi olmadığında baskın olmayan olarak kabul edilir. Cepheyi sıkılaştırmak için değişen parametrelerle skalerleştirme-çözme döngüsünü tekrarlayın.
Pareto cephesini destekleyici görselleştirmelerle (saçılım grafikleri, paralel koordinat grafikleri) karar vericilere sunun. Uygulama için baskın olmayan kümeden tercih edilen bir çözümü seçmek üzere çok kriterli karar kuralları, paydaş tercihleri veya sözlük sıralaması uygulayın.
Sık yapılan hatalar
- Dışbükey olmayan amaç uzaylarında ağırlıklı toplam yöntemini kullanmak, Pareto cephesinin tüm bölümlerini kaçıracaktır; bu gibi durumlarda epsilon-kısıtlama veya artırılmış başarı skalerleştirme fonksiyonlarını tercih edin.
- Tamsayı değişkenlerini bir gevşetmede sürekli olarak ele almak ve ardından yuvarlamak, Pareto-optimalitesini garanti etmez ve uygun olmayan veya baskın çözümler üretebilir.
- Çözmeden önce kısıtlama fazlalığını veya sıkılığını kontrol etmeyi ihmal etmek, çözümleyicilerin aşırı süre çalışmasına veya yanlış uygunsuzluk raporlamasına neden olabilir.
- Tüm Pareto çözümlerini filtreleme veya görselleştirme rehberliği olmadan karar vericilere sunmak, karar felcine yol açar; sonuçları her zaman yapılandırılmış seçim desteğiyle birlikte sunun.
- Çok az skalerleştirme çalıştırmasından sonra Pareto cephesinin tamamlandığını varsaymak, aşırı güvenli sonuçlara yol açabilir; toplanan tüm çözümler arasındaki baskın olmama durumunu kontrol ederek kapsamı doğrulayın.
Sık sorulan sorular
MO-MIP, standart çok amaçlı doğrusal programlamadan nasıl farklıdır?
Çok amaçlı LP'de tüm karar değişkenleri süreklidir, bu nedenle verimli Pareto çözümleri bir dışbükey politopun köşelerinde bulunabilir. MO-MIP, değişkenlerin bazılarının veya tamamının tamsayı değerli olmasını gerektirir, bu da uygun kümeyi dışbükey olmayan ve ayrık hale getirir, bu da simpleks tabanlı yöntemler yerine dal-sınır araması gerektirir.
NSGA-II gibi meta-sezgiselleri kesin MIP çözümleyicileri yerine kullanabilir miyim?
Evet, ve büyük ölçekli veya kombinatoryal olarak karmaşık problemler için meta-sezgiseller genellikle tercih edilir çünkü daha iyi ölçeklenirler. Takas, kesinlik garantisi olmayan yaklaşık Pareto cepheleri sağlamalarıdır, oysa kesin MO-MIP çözümleyicileri buldukları çözümler için baskın olmama garantisi verir.
Epsilon-kısıtlama yöntemi nedir ve neden tavsiye edilir?
Epsilon-kısıtlama yöntemi, bir amacı optimize ederken diğer tüm amaçları belirtilen sınırlardan (epsilonlar) daha kötü olmayacak şekilde kısıtlar. Ağırlıklı toplam yönteminin kaçırdığı dışbükey olmayan Pareto bölgelerindeki çözümleri keşfedebilir, bu da onu genel MO-MIP problemleri için daha güvenilir hale getirir.
Kaç Pareto çözümü üretmeliyim?
Amaç sayısına ve karar verme için gereken çözünürlüğe bağlıdır. İki amaç için, cepheyi karakterize etmek için genellikle 20-50 eşit aralıklı çözüm yeterlidir. Üç veya daha fazla amaç için sayı üstel olarak artar; çözüm aşırı yüklenmesini önlemek için etkileşimli veya tercih güdümlü yöntemler önerilir.
MO-MIP, verilerde belirsizlik içeren problemler için uygun mudur?
Standart MO-MIP deterministik verileri varsayar. Girdi verileri belirsiz olduğunda, sağlam optimizasyon veya stokastik programlama uzantılarıyla birleştirilmelidir - örneğin, iki aşamalı stokastik MO-MIP veya en kötü durum amaç sınırlarıyla sağlam MO-MIP.
İlgili yöntemler
Kaynaklar
Ehrgott, M. (2005). Multicriteria Optimization (2nd ed.). Springer, Berlin.
ISBN: 9783540213987Kopyalandı.Mavrotas, G. (2009). Effective implementation of the epsilon-constraint method in Multi-Objective Mathematical Programming problems. Applied Mathematics and Computation, 213(2), 455-465.
DOI kaynağını açKopyalandı.