Karmaşık-Tamsayı Programlama — Sürekli ve tamsayı kararlar üzerinde kesin optimizasyon
- Ortaya koyan
- Ralph Gomory (branch-and-bound cuts, 1958); Land & Doig (branch-and-bound, 1960)
- Yıl
- 1958–1960
- Tür
- Mathematical optimization
- Aile
- Simulation / optimization
Bu metin makine çevirisidir ve henüz incelenmedi. Asıl metni İngilizce oku
Ne işe yarar?
Karmaşık-Tamsayı Programlama (MIP), bazı karar değişkenlerinin tamsayı değerleri alması gerektiği, diğerlerinin ise sürekli olabileceği matematiksel bir optimizasyon çerçevesidir.
Doğrusal programlamayı genelleştirir ve operasyon araştırmaları, lojistik, çizelgeleme, kaynak tahsisi ve mühendislik tasarımında, bölünemezlik kısıtlarının — evet/hayır kararları veya tam birim miktarları gibi — doğal olarak ortaya çıktığı yerlerde yaygın olarak kullanılır.
Yöntemin mantığı
Birçok gerçek optimizasyon problemi, bölünemeyen kararlar içerir — bir tesisi ya açarsınız ya da açmazsınız, tam olarak bir işçiyi bir vardiyaya atarsınız, tam birimler sipariş edersiniz. Sürekli doğrusal programlama bu gerçekleri göz ardı eder ve uygulanamaz kesirli cevaplar üretebilir. MIP, doğrudan modelde bütünlüğü zorlar. Çözücü, dallanma ve sınırlama (branch-and-bound) yoluyla uygun tamsayı çözümlerin uzayını sistematik olarak araştırır: her bölgedeki en iyi olası çözümü sınırlamak için gevşetilmiş sürekli alt problemler çözer, şimdiye kadar bulunan en iyi tamsayı çözümünü iyileştiremeyen bölgeleri eler ve kesme düzlemleri ekleyerek aramayı sıkılaştırır. Sonuç, kanıtlanabilir şekilde optimal veya optimale yakın bir plandır.
Tarih
Tamsayı programlamanın temelleri, 1958'de kesme-düzlem yöntemini tanıtan Ralph Gomory ve 1960'ta dallanma ve sınırlamayı biçimlendiren Land ve Doig tarafından atıldı. Sonraki on yıllarda LP gevşetme teorisi, polihedral kombinatorik (Edmonds, Padberg, Grötschel) geliştirildi ve 1990'lara gelindiğinde ticari çözücüler büyük ölçekli MIP'yi pratik hale getirdi. Alan, Nemhauser ve Wolsey (1988) ve Wolsey (1998) tarafından kapsamlı bir şekilde ele alınmaktadır.
Ne zaman kullanılır?
Probleminiz doğrusal veya doğrusal hale getirilebilir bir amaç fonksiyonuna ve kısıtlamalara sahip olduğunda ve tamsayı değerli olması gereken kararlar (tesis yeri seçimi, mürettebat çizelgeleme, sermaye bütçelemesi, ağ tasarımı, kesme-stok problemleri) içerdiğinde MIP kullanın. Kanıtlanabilir şekilde optimal veya sınırlı boşluklu bir çözüm gerektirdiğinizde ve problem boyutu yönetilebilir olduğunda (modern çözücülerle binlerce değişken) tercih edilen yöntemdir. Amaç fonksiyonu veya kısıtlamalar yüksek derecede doğrusal olmadığında (bunun yerine doğrusal olmayan veya karmaşık-tamsayı doğrusal olmayan programlama kullanın), problem kesin yöntemler için yasaklayıcı derecede büyük olduğunda (sezgisel veya meta-sezgisel yöntemleri düşünün) veya sürekli yaklaşımlar yeterince doğru olduğunda (hız için LP kullanın) MIP kullanmayın.
Sınırlar ve dikkat edilmesi gerekenler
- En kötü durum karmaşıklığı NP-zorludur; çözüm süresi tamsayı değişkenlerinin sayısıyla üssel olarak artabilir.
- Kesin bir matematiksel formülasyon gerektirir; kötü formüle edilmiş modeller, altta yatan problem yönetilebilir olsa bile çözülemez olabilir.
- Dışbükey olmayan veya doğrusal olmayan öğeler, model karmaşıklığını artıran ek doğrusallaştırma veya özel çözücüler gerektirir.
- Çözücü lisans maliyetleri ticari araçlar için önemli olabilir, ancak yüksek kaliteli açık kaynaklı alternatifler mevcuttur.
- Sonuçlar yalnızca model kadar iyidir: yanlış kısıtlama belirlemesi anlamsız optimumlara yol açar.
Kaynak metnin koşulları, bağımsız bilimsel inceleme veya analiz motoru doğrulaması yerine geçmez.
Güçlü yönleri
- Kanıtlanabilir şekilde optimal çözümler üretir ve nicelendirilebilir bir optimalik boşluğu ile titiz karar gerekçelendirmesini sağlar.
- İkili ve genel tamsayı değişkenlerini yerel olarak ele alır, gerçek dünyadaki bölünemezlik ve mantıksal kısıtlamaları yakalar.
- Modern çözücüler (Gurobi, CPLEX, SCIP), büyük örnekleri verimli bir şekilde işlemek için gelişmiş dallanma ve sınırlama, kesme düzlemleri ve ön işlemeyi kullanır.
- Şeffaf model formülasyonu varsayımları açık hale getirir ve alan uzmanları tarafından denetlenebilir.
- Çözümlerin girdi verileriyle nasıl değiştiğini anlamak için duyarlılık analizi ve parametrik çalışmaları destekler.
- Hızlı prototipleme sağlayan modelleme dilleri (AMPL, GAMS, Pyomo, JuMP) tarafından yaygın olarak desteklenir.
Uygulama alanları
- Tedarik zinciri ve lojistik: araç rotalama, tesis yeri seçimi ve tamsayı sevkiyat miktarlarıyla envanter optimizasyonu.
- İşgücü çizelgeleme: hemşire nöbeti, mürettebat ataması ve ikili atama değişkenleriyle vardiya planlaması.
- Sermaye bütçelemesi: bütçe kısıtlamalarına tabi bölünemez yatırım projeleri portföyünün seçimi.
- Telekomünikasyon ve ağ tasarımı: ikili bağlantı etkinleştirme kararlarıyla kapasite genişletme ve yönlendirme.
- Enerji sistemleri: güç şebekelerinde her saat hangi jeneratörlerin açılıp kapanacağına karar veren birim taahhüdü.
- Üretim: parti büyüklükleri, makine çizelgeleme ve kesme-stok problemleriyle üretim lot büyüklüğü.
Nasıl çalışır?
Nasıl çalışır?
Optimizasyon modelini tanımlayın: bir amaç fonksiyonu (minimize veya maksimize edilecek karar değişkenlerinin doğrusal kombinasyonu), doğrusal eşitsizlik ve eşitlik kısıtları ve bütünlük gereksinimleri. Sürekli değişkenler kesirli olabilen miktarları; ikili (0/1) veya genel tamsayı değişkenleri ayrık kararları ele alır.
Formül
\min_{x,y}\; c^\top x + d^\top y \quad \text{s.t.}\; Ax + By \leq b,\; x \geq 0,\; y \in \mathbb{Z}^pBütünlük kısıtlarını geçici olarak atarak LP gevşetmesini çözün. Bu, optimal MIP amacı için bir alt sınır (minimize etme için) ve kesirli olabilen bir aday çözüm verir.
Formül
\text{LP relaxation: replace } y \in \mathbb{Z}^p \text{ with } y \geq 0LP gevşetme çözümünden kesirli bir tamsayı değişkeni seçin. Birinde taban kısıtlaması, diğerinde tavan kısıtlaması ekleyerek iki alt problem oluşturun, herhangi bir tamsayı-uygun noktayı kaybetmeden uygun uzayı bölümleyin.
Formül
\text{Select fractional } y_j^*; \text{ create subproblems: } y_j \leq \lfloor y_j^* \rfloor \text{ and } y_j \geq \lceil y_j^* \rceilHer alt problemin LP gevşetmesini çözün. Sınır, şimdiye kadar bulunan en iyi tamsayı çözümünden (incumbent) daha kötüyse, o dalı budayın. LP çözümü tamsayı-uygunsa, amacı iyileştiriyorsa incumbent'ı güncelleyin.
Formül
\text{Prune node if LP bound} \geq \text{incumbent; update incumbent when integer-feasible solution found}Kesme düzlemleri ekleyin — kesirli LP çözümünü tamsayı-uygun herhangi bir noktayı kaldırmadan kesen geçerli eşitsizlikler. Gomory kesmeleri klasik yaklaşımdır; probleme özgü kesmeler (örn. clique kesmeleri, flow kesmeleri) ağaç boyutunu önemli ölçüde azaltabilir.
Formül
\text{Add Gomory or problem-specific cutting planes to tighten LP relaxation before branching}Dallanma ve sınırlama ağacı tamamen keşfedildiğinde veya en iyi tamsayı çözüm ile küresel alt sınır arasındaki fark kullanıcı tarafından belirtilen bir tolerans dahilinde (örn. %0.01) düştüğünde durun. Optimalik sertifikası ile incumbent çözümü döndürün.
Formül
\text{Stop when all nodes pruned; return incumbent } x^*, y^* \text{ with optimality gap} \leq \epsilonSık yapılan hatalar
- Çok sıkı bir optimalik boşluk toleransı seçmek çözücünün süresiz çalışmasına neden olabilir; büyük örnekler için her zaman pratik bir boşluk (%1 gibi) ayarlayın.
- Modeldeki simetri (örn. değiştirilebilir tesisler), gereksiz dallar oluşturur ve arama ağacını şişirir — simetri kırma kısıtlamaları kullanın.
- Zayıf LP gevşetmeleri (büyük bütünlük boşluğu), çok büyük dallanma ve sınırlama ağaçlarına yol açar; geçerli eşitsizlikler eklemeye veya formülasyonu sıkılaştırmaya zaman ayırın.
- Sadece bazılarının ihtiyaç duyması gerekirken tüm değişkenleri tamsayı olarak ele almak gereksiz yere maliyetlidir; ikili değişkenleri yalnızca mantıksal kısıtlamaların gerektirdiği yerlerde kullanın.
- İyi bir başlangıç uygun çözümüyle sıcak başlama (warm-starting) yok saymak, ilk incumbent'ı bulmak için çözücü zamanını boşa harcar.
Sık sorulan sorular
MIP, doğrusal programlamadan (LP) nasıl farklıdır?
LP, tüm karar değişkenlerinin sürekli (gerçek değerli) olmasını gerektirir, bu da fiziksel olarak uygulanamayan kesirli çözümler (örn. 2.7 kamyon) verebilir. MIP, bazı veya tüm değişkenlere bütünlük kısıtlamaları ekleyerek, daha büyük hesaplama karmaşıklığı pahasına tam sayı veya ikili çözümler zorlar.
Ne zaman MIP yerine bir sezgisel yöntem kullanmalıyım?
Problem milyonlarca değişkene, yüksek derecede doğrusal olmayan yapıya sahip olduğunda veya gerçek zamanlıya yakın bir çözüme ihtiyaç duyduğunda, kesin MIP çok yavaş olabilir. Meta-sezgisel yöntemler (genetik algoritmalar, simüle tavlama) hızlı bir şekilde iyi çözümler üretebilir, ancak optimalik garantisi olmadan. Çözüm kalitesi sertifikasının önemli olduğu durumlarda MIP tercih edilir.
Optimalik boşluğu nedir ve ne kadar küçük olmalıdır?
Boşluk, (incumbent amacı - LP sınırı) / LP sınırı olarak yüzde olarak ifade edilir. Bilinen en iyi çözümün gerçek optimumdan ne kadar uzakta olabileceğini belgeler. Çoğu pratik uygulama için %0.1–1'lik bir boşluk yeterlidir; daha sıkı boşluklar üssel olarak daha fazla çözücü süresi gerektirir.
MIP, doğrusal olmayan amaçları veya kısıtlamaları ele alabilir mi?
Standart MIP doğrusallığı varsayar. Doğrusal olmayan ilişkiler doğrusal hale getirilmeli (örn. parçalı-doğrusal yaklaşım, çarpımların ikili genişletilmesi) veya önemli ölçüde çözülmesi daha zor olan karmaşık-tamsayı doğrusal olmayan programlama (MINLP) çözücüleri tarafından ele alınmalıdır.
MIP için hangi çözücüler önerilir?
Ticari: Gurobi ve CPLEX endüstri standartlarıdır. Açık kaynak: SCIP, CBC (COIN-OR aracılığıyla) ve HiGHS orta ölçekli problemler için rekabetçidir. Hepsi AMPL, Pyomo ve JuMP gibi standart modelleme arayüzlerini destekler.
İlgili yöntemler
Kaynaklar
Nemhauser, G. L., Wolsey, L. A. (1988). Integer and Combinatorial Optimization. Wiley-Interscience, New York.
ISBN: 9780471359432Kopyalandı.Wolsey, L. A. (1998). Integer Programming. Wiley-Interscience, New York.
ISBN: 9780471283669Kopyalandı.