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

Deterministik Tamsayı Programlama — Tamsayı Karar Değişkenleriyle Kesin Optimizasyon

Ortaya koyan
Ralph E. Gomory
Yıl
1958
Tür
Exact combinatorial optimization
Aile
Simulation / optimization

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

Yazı boyutu

Ne işe yarar?

Deterministik Tamsayı Programlama (DIP), bazı veya tüm karar değişkenlerinin tam olarak bilinen (deterministik) amaç ve kısıt verileri verildiğinde tamsayı değerler alması gereken problemler için en iyi çözümü bulan matematiksel bir optimizasyon yaklaşımıdır.

Bu, 1950'lerin sonlarından beri operasyon araştırmaları ve kombinatoryal optimizasyonun temeli olan tamsayı programlamanın klasik, stokastik olmayan biçimidir.

Yöntemin mantığı

Birçok gerçek dünya kararı doğası gereği ayrık: bir tesisi açarsınız ya da açmazsınız; bir çalışanı bir vardiyaya atarsınız ya da atamazsınız. Sürekli optimizasyon yöntemleri bu tam sayı gereksinimlerini zorunlu kılamaz. Deterministik Tamsayı Programlama, değişkenleri tamsayılara kısıtlayarak ve tüm problem parametreleri — maliyetler, kapasiteler, talepler — kesin olarak bilindiğinde bunu ele alır. Sonuç, bu kesinlik varsayımı altında kanıtlanabilir şekilde kesin, optimal bir çözümdür ve bu da onu tamsayı programlamanın stokastik ve sağlam (robust) varyantlarıyla karşılaştırıldığı referans formülasyonu haline getirir.

Tarih

Tamsayı programlama, 1950'lerin sonlarında doğrusal programlamadan ortaya çıktı. Ralph Gomory'nin 1958 kesme düzlemi algoritması ilk sistematik kesin yöntemdi. Dallanma ve sınır (Land ve Doig, 1960) ile eş zamanlı olarak, bu yaklaşımlar alanı tanımladı. 'Deterministik' sıfatı, klasik formülasyonu stokastik tamsayı programlamadan (Birge ve Louveaux, 1997) ayırır ve belirsizlik farkındalığı olan varyantlar çoğaldıkça standart terminoloji haline geldi.

Ne zaman kullanılır?

Deterministik Tamsayı Programlamayı şu durumlarda kullanın: (1) karar değişkenleri doğası gereği ayrık olduğunda (atama, çizelgeleme, tesis yeri seçimi, kutu paketleme, ağ tasarımı); (2) tüm problem parametreleri kesin olarak bilindiğinde veya nokta değerleri olarak güvenilir bir şekilde tahmin edilebildiğinde; (3) kesin optimal bir çözüm gerektiğinde, sezgisel bir yaklaşıma tercih edildiğinde. Şu durumlarda KULLANMAYIN: parametreler belirsiz veya senaryoya bağlı olduğunda (bunun yerine stokastik veya sağlam tamsayı programlamayı kullanın); problem ölçeği dallanma ve sınırın hesaplama açısından çözülemez olduğu ve sezgisel yöntemlerin kabul edilebilir olduğu kadar büyük olduğunda; değişkenler gerçekten sürekli olduğunda (LP kullanın); veya birden fazla çelişkili amaç eş zamanlı olarak dengelenmelidir (çok amaçlı tamsayı programlamayı kullanın).

Sınırlar ve dikkat edilmesi gerekenler

  • Tüm problem parametrelerinin tam olarak bilindiğini varsayar — gerçek dünya belirsizliği tasarımsal olarak göz ardı edilir.
  • Genel olarak NP-zor; en kötü durum çözüm süresi problem boyutuna göre üstel olarak artar.
  • Büyük kombinatoryal problemler, modern çözücülerle bile saatler veya günler süren hesaplama gerektirebilir.
  • Model formülasyon kalitesi (kısıt sıkılığı, simetri kırma) çözüm süresini önemli ölçüde etkiler.

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

Güçlü yönleri

  • Deterministik model varsayımları dahilinde kanıtlanabilir bir optimal çözüm garanti eder.
  • Sürekli yöntemlerin yapamadığı ayrık, kombinatoryal karar yapılarını doğal olarak ele alır.
  • Olgun, oldukça verimli ticari ve açık kaynaklı çözücüler (CPLEX, Gurobi, SCIP) tarafından desteklenir.
  • Büyük örnekler için ilkeli erken sonlandırmayı sağlayan bir optimalite boşluğu sertifikası sağlar.
  • Sezgisel ve stokastik varyantları karşılaştırmak için altın standart referans formülasyonu olarak hizmet eder.

Uygulama alanları

  • Ayrık makine veya işgücü kaynaklarıyla üretim planlama ve çizelgeleme
  • Tesis yeri seçimi: hangi depoların veya fabrikaların açılacağına karar verme
  • Ulaşım ve lojistikte araç rotalama ve mürettebat çizelgeleme
  • Sermaye bütçelemesi: bölünemez yatırım projeleri portföyü seçme
  • Sabit bağlantı kurma maliyetleriyle telekomünikasyon ağı tasarımı
  • Sağlık personeli çizelgeleme ve ameliyathane çizelgeleme

Nasıl çalışır?

Nasıl çalışır?

1

Optimizasyon modelini tanımlayın: tamsayı karar değişkenlerinin doğrusal bir kombinasyonu olarak minimize edilecek (veya maksimize edilecek) bir amaç fonksiyonu, bir dizi doğrusal eşitsizlik veya eşitlik kısıtına tabi olarak. Tüm katsayılar (c, A, b) sabittir ve bilinmektedir — formülasyonu deterministik yapan budur. İkili değişkenler (0/1) evet/hayır kararları için özel bir durumdur.

Formül
\min \; c^\top x \quad \text{s.t.} \quad Ax \leq b,\; x \geq 0,\; x \in \mathbb{Z}^n
2

Değişkenlerin geçici olarak sürekli değerler almasına izin veren LP gevşetmesini çözün. Bu, optimal tamsayı amaç için bir alt sınır verir. LP gevşetme çözümü zaten tamsayı değerliyse, IP için optimaldir; aksi takdirde dallanma başlar.

Formül
\text{Solve LP relaxation: } \min \; c^\top x \quad \text{s.t.} \quad Ax \leq b,\; x \geq 0
3

LP gevşetme çözümünden kesirli bir değişken seçin ve bir kolda taban kısıtlaması (x_j <= taban değeri) ve diğer kolda tavan kısıtlaması (x_j >= tavan değeri) ekleyerek uygun bölgeyi bölün, özyinelemeli olarak çözülecek iki alt problem oluşturun.

Formül
\text{Select fractional variable } x_j^*. \text{ Create two subproblems: } x_j \leq \lfloor x_j^* \rfloor \text{ and } x_j \geq \lceil x_j^* \rceil
4

Her alt problemin LP gevşetmesini bir sınır elde etmek için çözün. Bir düğümün sınırı, bilinen en iyi tamsayı çözümünden (incumbent) daha kötüyse, onu budayın. Alt problem, incumbent'tan daha iyi tamsayıya uygun bir çözüm üretirse, incumbent'ı güncelleyin. Süreç bir dallanma ve sınır (branch-and-bound) arama ağacı oluşturur.

Formül
\text{Compute bounds; prune nodes where LP bound} \geq \text{incumbent. Update best integer solution.}
5

Kesme düzlemi yöntemleri — en önemlisi Gomory kesmeleri — LP tablosundan, tüm tamsayı çözümleri tarafından sağlanan ancak mevcut kesirli LP çözümü tarafından ihlal edilen ek doğrusal eşitsizlikler türetir. Bu kesmeleri eklemek LP gevşetmesini sıkılaştırır ve dallanmayı azaltır. Modern çözücüler, dallanma ve kesme (branch-and-cut) çerçevesinde dallanma ve sınır ile kesmeleri birleştirir.

Formül
\text{Optionally add Gomory cuts or problem-specific valid inequalities to tighten LP relaxation.}
6

Algoritma, açıkta kalan tüm düğümler budandığında veya tamsayı çözümleri ürettiğinde sonlanır. Sonlandırmadaki incumbent, kanıtlanabilir şekilde optimal tamsayı çözümdür. Çözücüler ayrıca, büyük problemler için bir durdurma kriteri olarak kullanılabilecek en iyi sınır ile incumbent arasındaki bir boşluk rapor eder.

Formül
\text{Return optimal integer solution } x^* \text{ with objective value } z^* = c^\top x^*

Sık yapılan hatalar

  • Belirsiz parametreleri deterministik nokta tahminleri olarak ele almak, pratikte kötü performans gösteren çözümler üretebilir — uygulamadan önce bu varsayımı doğrulayın.
  • Zayıf LP gevşetmeleri (büyük bütünlük boşlukları) devasa dallanma ve sınır ağaçlarına yol açar; ölçeklendirmeden önce geçerli eşitsizliklere ve yeniden formülasyona yatırım yapın.
  • Büyük-M formülasyonlarından kaynaklanan ikili değişken patlaması, LP gevşetmesini sayısal olarak kararsız hale getirebilir; daha sıkı kısıt yeniden formülasyonlarını tercih edin.
  • Sıfır olmayan bir boşluk toleransı kullanırken uygunluğu optimalite ile karıştırmak — her zaman amaç değerinin yanında boşluğu rapor edin.
  • Modellerdeki simetriyi (örneğin, özdeş makineler veya işçiler) göz ardı etmek, gereksiz dallanmaya neden olur; simetri kırma kısıtlamaları ekleyin.

Sık sorulan sorular

Deterministik tamsayı programlamayı stokastik tamsayı programlamadan ayıran nedir?

Deterministik Tamsayı Programlamada tüm amaç ve kısıt parametreleri sabittir ve bilinir. Stokastik Tamsayı Programlama, belirsiz parametreleri olasılık dağılımları veya senaryolar aracılığıyla açıkça modeller, bu senaryolar boyunca sağlam veya beklenen optimal çözümler üretir. Deterministik Tamsayı Programlama daha basittir ve çözmesi daha hızlıdır ancak belirsizliği göz ardı eder.

İkili programlama, tamsayı programlamanın özel bir durumu mudur?

Evet. İkili (0-1) programlama, her karar değişkenini {0, 1} ile sınırlar. Bir tesisi açıp açmama, bir proje seçme veya bir çalışanı atama gibi evet/hayır kararları için kullanılan en yaygın özel durumdur. Genel tamsayı programlama herhangi bir negatif olmayan tamsayı değerine izin verir.

Deterministik Tamsayı Programlamadan ne zaman bir sezgisel yönteme geçmeliyim?

Dallanma ve sınır ağacı kabul edilebilir bir zaman sınırı içinde keşfedilemeyecek kadar büyük olduğunda ve iyi bir sezgisel yöntemin (genetik algoritma, simüle tavlama, büyük komşuluk arama) optimalite boşluğu uygulama için tolere edilebilir olduğunda. Kesin optimizasyondan saparken boşluğu rapor edin ve gerekçelendirin.

Deterministik Tamsayı Programlama doğrusal olmayan amaçları veya kısıtları ele alabilir mi?

Klasik deterministik Tamsayı Programlama, doğrusalığı varsayar (tamsayı doğrusal programlama). Doğrusal olmayan tamsayı programlama mevcuttur ancak önemli ölçüde daha zordur; birçok doğrusal olmayan biçim, yardımcı ikili değişkenler ve büyük-M yeniden formülasyonları aracılığıyla doğrusal hale getirilebilir. Karesel tamsayı programlama (QIP), bazı modern çözücüler tarafından doğrudan desteklenir.

Pratikte deterministik Tamsayı Programlama için hangi çözücüyü kullanmalıyım?

Ticari: En iyi performans için Gurobi veya IBM CPLEX. Akademik/açık kaynak: SCIP, CBC (COIN-OR aracılığıyla) veya HiGHS. Hepsi otomatik ön işlemenin yanı sıra dallanma ve kesme uygular. Python kullanıcıları için PuLP, Pyomo veya scipy.optimize.milp uygun modelleme arayüzleri sağlar.

İlgili yöntemler

Kaynaklar

  1. Gomory, R. E. (1958). Outline of an algorithm for integer solutions to linear programs. Bulletin of the American Mathematical Society, 64(5), 275-278.

    DOI kaynağını aç
    Kopyalandı.
  2. Wolsey, L. A. (1998). Integer Programming. Wiley-Interscience, New York.

    ISBN: 9780471283669
    Kopyalandı.