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

Tamsayı Programlama — IP ve Karma Tamsayı Programlama (MIP)

Ortaya koyan
Ralph Gomory (cutting planes, 1958); land-and-doig branch-and-bound (1960)
Yıl
1958
Tür
Mathematical optimisation — exact combinatorial method

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

Yazı boyutu

Ne işe yarar?

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.

Yöntemin mantığı

Sıradan doğrusal programlama, sürekli bir uygun bölgedeki en iyi noktayı bulur. Ancak birçok gerçek karar kesiklidir — 2.7 hemşire görevlendiremez veya yarım depo açamazsınız. Tamsayı programlama, bazı veya tüm değişkenlerin tam sayılar (veya ikili 0/1 seçimler) olması gerektiği kısıtlamasını ekler. Bu kısıtlamanın bedeli hesaplamalıdır: uygun küme artık pürüzsüz bir yüzey değil, dağınık bir nokta kümesidir ve en iyisini bulmak, muazzam sayıda aday çözümü incelemeyi gerektirebilir. Çözücüler, problemi akıllıca daha küçük alt problemlere (dallanma) bölerek ve şimdiye kadar bulunan en iyi çözümü geçemeyecek dalları budayarak (sınırlandırma) ve aynı zamanda ek eşitsizlikler (kesme düzlemleri) aracılığıyla sürekli yaklaşımı sıkılaştırarak bunu yönetir.

Tarih

Tamsayı programlama, araştırmacıların doğrusal programlamayı kesikli kararlara genişletmeye çalıştığı 1950'lerin sonlarında ortaya çıktı. Ralph Gomory, 1958'de kesme düzlemi yöntemini sistematik olarak tanıttı ve herhangi bir tamsayı programının sonlu sayıda kesme eklenerek prensipte çözülebileceğini kanıtladı. Land ve Doig (1960), alanın hala güvendiği kanonik ders kitabı tedavilerini sağlayan baskın kesin algoritma haline gelen dal-ve-sınır'ı biçimlendirdi. Pratik devrim, her iki tekniği gelişmiş sezgisel yöntemlerle birleştiren dal-ve-kesme çözücülerinin geliştirilmesiyle ve daha sonra büyük ölçekli gerçek dünya uygulamalarını bugün mümkün kılan ticari ve açık kaynaklı çözücü performansının patlamasıyla geldi.

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.

Sınırlar ve dikkat edilmesi gerekenler

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

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

Güçlü yönleri

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

Uygulama alanları

  • Personel ve hemşire çizelgeleme — çalışma saati düzenlemelerine uyarken kapsama gereksinimlerini karşılamak için vardiyaları atama.
  • Araç yönlendirme ve lojistik — kapasite ve zaman penceresi kısıtlamaları altında minimum maliyetli teslimat rotalarını bulma.
  • Tesis konumu — toplam dağıtım maliyetini en aza indirmek için hangi depoların veya fabrikaların açılacağına karar verme.
  • Sermaye bütçelemesi — toplam getiriyi en üst düzeye çıkarmak için bir bütçe dahilinde yatırım projeleri portföyü seçme.
  • Üretim planlaması — kurulum maliyetleri ve stok maliyetlerini dengelemek için zaman periyotları boyunca tamsayı parti boyutlarını belirleme.
  • Ağ tasarımı — bir iletişim veya ulaşım ağında hangi bağlantıların kurulacağını seçme.

Nasıl çalışır?

Nasıl çalışır?

1

Problem matematiksel bir program olarak kurulur: karar değişkenlerini tanımlayın (gerektiğinde tamsayı veya ikili olarak beyan edilmelidir), en aza indirmek veya en üst düzeye çıkarmak için doğrusal bir amaç fonksiyonu yazın ve tüm doğrusal kısıtlamaları listeleyin. Sıkı bir formülasyon — sürekli (LP) gevşetmesi gerçek tamsayı optimumuna mümkün olduğunca yakın olan — çözüm süresini önemli ölçüde azaltır.

2

Tamsayı kısıtlamaları, LP gevşetmesini elde etmek için geçici olarak kaldırılır. Bu gevşetmeyi çözmek hızlıdır ve bir sınır verir: optimum değeri her zaman gerçek tamsayı optimumundan en azından daha iyidir (en aza indirme için bir alt sınır). Gevşetme çözümü tesadüfen tamamen tamsayı ise, problem çözülmüş olur. Aksi takdirde, gevşetme ile tamsayı arasındaki fark arama yönlendirir.

3

Gevşetme çözümündeki kesirli bir değişken seçilir ve problem iki alt probleme ayrılır — biri değişkenin aşağı yuvarlanmasını, diğeri yukarı yuvarlanmasını gerektirir. Her alt problem kendi başına gevşetilir ve çözülür, bir arama ağacı oluşturulur. Gevşetme sınırının şimdiye kadar bulunan en iyi tamsayı çözümünden daha kötü olduğu dallar, daha fazla keşif yapılmadan budanır.

4

Kesme düzlemleri, herhangi bir tamsayı uygun noktayı kaldırmadan LP-gevşetme uygun bölgesinin bir kısmını kesen geçerli doğrusal eşitsizliklerdir. Güçlü kesmelerin (Gomory kesmeleri, kapak eşitsizlikleri, klik kesmeleri) eklenmesi LP sınırını sıkılaştırır ve çözücünün keşfetmesi gereken düğüm sayısını azaltır.

5

Tüm keşfedilen düğümlerde bulunan en iyi tamsayı uygun çözüm optimum olarak döndürülür. Optimizasyon boşluğu — en iyi tamsayı çözüm ile kalan en iyi sınır arasındaki yüzde farkı — raporlanır; sıfır boşluk küresel optimalliği belgeler. Büyük NP-zor örnekler için, çözücü kullanıcı tarafından belirtilen bir boşluk toleransı ile erken sonlanabilir ve kanıtlanabilir bir sınıra sahip, optimuma yakın bir çözüm döndürebilir.

Sık yapılan hatalar

  • Sürekli değişkenleri tamsayı olması gerekirken sürekli olarak — veya tam tersi — beyan etmek sessizce yanlış çözümler üretir; her zaman değişken türlerinin problemin fiziksel gerçekliğine uyduğundan emin olun.
  • Aşırı dallanmaya neden olan zayıf bir LP gevşetme boşluğuna sahip gevşek bir formülasyon; çözmeden önce formülasyon sıkılaştırmasına (güçlü eşitsizlikler, simetri kırma) zaman ayırın.
  • Çözücü çıktısındaki tamsayı boşluğunu göz ardı etmek: raporlanan bir amaç değeri, yalnızca bulunan en iyi tamsayı çözümüdür, boşluk sıfır olmadıkça küresel optimum değildir.
  • Amaç veya kısıtlamaları doğrusal olmayan problemleri uygun MINLP işlemi olmadan IP'ye uygulamak yanlış modellere yol açacaktır.
  • Çizelgeleme veya yönlendirme problemleri için, geçerli eşitsizlikleri (klik veya kapak kesmeleri gibi) eklememek önemli performans kazançlarını masada bırakır.

Sık sorulan sorular

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.

İlgili yöntemler

Kaynaklar

  1. Wolsey, L.A. (1998). Integer Programming. Wiley.

    ISBN: 9780471283669
    Kopyalandı.
  2. Nemhauser, G.L. & Wolsey, L.A. (1988). Integer and Combinatorial Optimization. Wiley.

    ISBN: 9780471359432
    Kopyalandı.