Tamsayı Programlama — IP ve Karma Tamsayı Programlama (MIP)
Integer Programming (IP / Mixed-Integer Programming) · Ayrıca şöyle bilinir: IP, MIP, mixed-integer programming, mixed-integer linear programming, MILP, Tam Sayılı Programlama (IP / MIP)
Tamsayı programlama (IP), değişkenlerin yalnızca bir kısmının tam sayılara kısıtlandığı durumlarda karma tamsayı programlama (MIP) olarak da adlandırılır, matematiksel optimizasyonun, karar değişkenlerinin tamamının veya bir kısmının tamsayı veya ikili değerler alması gereken bir dalıdır. Doğrusal programlamanın üzerine inşa edilen bu yöntem, Ralph Gomory'nin kesme düzlemi yöntemi (1958) ve Land-Doig'in dal-ve-sınır algoritması (1960) ile biçimlendirilmiş ve o zamandan beri çizelgeleme, atama, yönlendirme ve kaynak tahsisi sorunları için standart kesin çerçeve haline gelmiştir.
Tam yöntemi oku
Bu bölümü okumak için ücretsiz hesapla giriş yapın.
Yöntem haritası
İlişkili yöntemlerin komşuluğu — keşfetmek için bir düğüm seçin.
Ne zaman kullanılır
Kararların doğası gereği kesikli olduğu — ikili evet/hayır seçimleri, tamsayı miktarları veya mantıksal açık/kapalı kısıtlamalar — ve kanıtlanabilir kalite sınırına sahip kesin veya optimuma yakın bir çözüm gerektiğinde tamsayı programlamayı kullanın. Çizelgeleme, mürettebat ve kaynak atama, araç yönlendirme, tesis konumu, sermaye bütçelemesi ve portföy seçimi için uygundur. IP istatistiksel bir çıkarım prosedüründen ziyade deterministik bir optimizasyon çerçevesi olduğundan, minimum örneklem boyutu gereksinimi yoktur. Değişken türleri ikili, kategorik (ikili olarak kodlanmış) veya sürekli (karma tamsayı durumunda) olabilir. Temel pratik gereksinim, problemin doğrusal bir amaç ve doğrusal kısıtlamalarla modellenebilmesidir; amaç veya kısıtlamalar doğrusal değilse, karma tamsayı doğrusal olmayan programlama (MINLP) uzantıları gereklidir.
Güçlü yönler & sınırlılıklar
- Sezgisel yöntemlerin kalite garantisi sunmadığının aksine, kanıtlanmış optimizasyon boşluğuna sahip kesin optimum çözümler üretir.
- İkili ve genel tamsayı değişkenlerini yerel olarak işler, bu da onu kombinatoryal kararlar için doğal çerçeve haline getirir.
- Çizelgeleme, yönlendirme, atama, sırt çantası gibi çok çeşitli alan problemlerine aynı matematiksel makine ile uygulanabilir.
- Modern dal-ve-kesme çözücüleri, on yıllar önce çözülemez olan milyonlarca değişken ve kısıtlamaya sahip problemleri çözebilir.
- Tamsayı programlama genel olarak NP-zorludur; çözüm süresi problem boyutuna göre üssel olarak artabilir ve kötü formülasyon.
- Zayıf bir LP gevşetmesi (büyük tamsayı boşluğu), derin, pahalı arama ağaçlarına ve uzun çalışma sürelerine yol açar.
- Büyük kardinaliteli kategorik değişkenlerin ikili genişletilmesi model boyutunu şişirebilir.
- Çok büyük örnekler için, çözücüler sıfır boşluğa ulaşmak yerine bir boşluk toleransı ile erken sonlandırılmalıdır.
SSS
IP ve MIP arasındaki fark nedir?
Saf tamsayı programlamada (IP) her karar değişkeni bir tamsayı olmalıdır. Karma tamsayı programlamada (MIP), bazı değişkenler tamsayı veya ikili iken diğerlerinin sürekli olmasına izin verilir. MIP, çoğu gerçek problem kesikli seçimleri sürekli miktarlarla karıştırdığı için pratikte daha genel ve daha yaygın kullanılan çerçevedir.
Doğrusal programlama polinomiyel ise tamsayı programlama neden NP-zorludur?
Doğrusal programlama, dışbükey bir politop üzerinde optimize eder ve simpleks veya iç nokta yöntemleriyle polinom zamanda çözülebilir. Tamsayı kısıtlamaları eklemek bu dışbükeyliği parçalar: uygun küme sonlu ama potansiyel olarak astronomik derecede büyük bir tamsayı noktaları kümesi haline gelir ve genel olarak en iyisini bulmak için polinom zamanlı bir algoritma bilinmemektedir. LP gevşetmesi bir sınır sağlar ancak doğrudan bir çözüm sağlamaz.
Çözümümün optimal olduğunu nasıl anlarım?
Çözücü bir optimizasyon boşluğu raporlar — bulunan en iyi tamsayı çözüm ile kalan en iyi alt sınır arasındaki yüzde farkı. %0 boşluk küresel optimalliği belgeler. Büyük problemler için bir boşluk toleransı (%1 gibi) ayarlayabilir ve optimuma yakın bir çözüm kabul edebilirsiniz; sınır, gerçek optimumun o yüzdeden daha iyi olamayacağını garanti eder.
Nasıl bir 'sıkı' formülasyon yapılır ve neden önemlidir?
Sıkı bir formülasyon, LP gevşetmesinin tamsayı optimumuna yakın bir sınır verdiği, küçük bir tamsayı boşluğu bırakan bir formülasyondur. Boşluk küçük olduğunda, dal-ve-sınır daha az düğüm keşfetmeli ve daha hızlı sonlanmalıdır. Gomory kesmeleri, kapak eşitsizlikleri veya klik kesmeleri gibi geçerli eşitsizliklerin eklenmesi formülasyonu sıkılaştırır ve genellikle bir çözücüyü hızlandırmanın en etkili yoludur.
Kaynaklar
- Wolsey, L.A. (1998). Integer Programming. Wiley. ISBN: 9780471283669
- Nemhauser, G.L. & Wolsey, L.A. (1988). Integer and Combinatorial Optimization. Wiley. ISBN: 9780471359432
Bu sayfayı kaynak gösterin
ScholarGate. (2026, June 1). Integer Programming (IP / Mixed-Integer Programming). ScholarGate. https://scholargate.app/tr/optimization/integer-programming
Hangi yöntem?
Bu yöntemi en yakın akrabalarının yanına koyup yan yana okuyun — kütüphane kitapları masaya serer; seçim sizindir.
- Kısıt ProgramlamaOptimizasyon↔ karşılaştır
- Dinamik ProgramlamaOptimizasyon↔ karşılaştır
- Hedef ProgramlamaKarar verme↔ karşılaştır
- Doğrusal ProgramlamaOptimizasyon↔ karşılaştır