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

Dal ve Sınır (Branch and Bound)

Ortaya koyan
Ailsa Land & Alison Doig
Yıl
1960
Tür
Exact combinatorial optimization algorithm
Aile
Mathematical programming

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

Yazı boyutu

Ne işe yarar?

Dal ve Sınır, bir ağaç yapısı üzerinde alt problemler halinde organize edilen, alt dalları budamak için gevşetme-türetilmiş üst sınırlar kullanan ve global olarak en iyi tamsayı çözümünü bulmayı garanti eden, kombinatoryal ve tamsayı optimizasyon problemleri için sistematik bir kesin algoritmadır. 1960 yılında Ailsa Land ve Alison Doig tarafından tanıtılmıştır.

Yöneylem araştırması, lojistik, çizelgeleme ve mühendislik tasarımında kullanılan modern karma-tamsayı programlama çözücülerinin temelini oluşturur.

Yöntemin mantığı

Geniş bir oda labirentinde saklı en yüksek değerli eşyayı aradığınızı hayal edin. Her odayı kontrol etmek yerine, her koridora girmeden önce oradan ulaşılabilecek maksimum olası değeri tahmin edersiniz. Eğer bu tavan, elinizde zaten bulunan en iyi eşyadan daha düşükse, tüm koridoru içeri bakmadan atlarız. Dal ve Sınır da aynı şekilde çalışır: problemi daha küçük parçalara böler, her parça için iyimser üst sınırlar hesaplar ve mevcut en iyi çözümü kanıtlanabilir şekilde geçemeyecek herhangi bir parçayı hemen eler.

Tarih

Land ve Doig, 1960 yılında Econometrica'da temel Dal ve Sınır makalesini yayınlayarak bunu ayrık programlama için otomatik bir yöntem olarak çerçevelediler. Little ve diğerleri (1963), tek gezgin satıcı problemine tekniği uygulayarak kombinatoryal optimizasyondaki rolünü pekiştirdiler. Dakin (1965), bugün en yaygın kullanılan biçim olan LP-gevşetme dallanmasını tanıttı. Sonraki on yıllarda kesme düzlemlerinin (dal ve kesme; branch-and-cut) ve sütun üretiminin (dal ve fiyat; branch-and-price) entegrasyonu görüldü ve Dal ve Sınır, tüm büyük ticari tamsayı programlama çözücülerinin motoru haline geldi.

Ne zaman kullanılır?

Kanıtlanabilir şekilde optimal çözümü karma-tamsayı veya saf-tamsayı doğrusal bir program için bulmanız gerektiğinde ve yaklaşık bir cevabı kabul edemediğinizde Dal ve Sınır'ı kullanın. Faydalı sınırlar sağlayan doğrusal (veya dışbükey) gevşetmelerle formüle edilebilen problemleri varsayar. Sayım ağacının patladığı çok büyük örnekler, sıkı gevşetmeler olmayan doğrusal olmayan tamsayı programları veya hesaplama süresinin kesin olarak sınırlı olduğu gerçek zamanlı ayarlar için daha az uygundur. Bu gibi durumlarda, sezgisel yöntemler veya meta-sezgisel yöntemler tercih edilebilir.

Sınırlar ve dikkat edilmesi gerekenler

  • En kötü durum karmaşıklığı üsteldir; kötü yapılandırılmış örneklerde ağaç aşırı derecede büyüyebilir.
  • Performans, dallanma değişkeni ve düğüm seçimi stratejisinin seçimine oldukça duyarlıdır.
  • Anlamlı üst sınırlar sağlayan hesaplanabilir bir gevşetme gerektirir; zayıf sınırlar minimum budamaya yol açar.
  • Aynı anda depolanması gereken birçok açık düğüm olduğunda bellek gereksinimleri önemli olabilir.

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

Güçlü yönleri

  • Tamsayı ve kombinatoryal programlar için global optimalliği garanti eder.
  • Sınır tabanlı budama yoluyla arama süresini çarpıcı biçimde azaltır — genellikle tam sayım ağacının yalnızca küçük bir kısmı keşfedilir.
  • Esnektir: daha fazla verimlilik için kesme düzlemleri (dal ve kesme; branch-and-cut) veya sezgisel sınırlar (dal ve fiyat; branch-and-price) içerebilir.
  • Olgun ticari çözücülerde (CPLEX, Gurobi) ve açık kaynaklı araçlarda (GLPK, CBC) yaygın olarak uygulanmıştır.

Uygulama alanları

  • Yöneylem araştırmasında havayolu mürettebatı çizelgeleme ve filo atama.
  • Tedarik zinciri ağ tasarımı ve tesis yeri belirleme problemleri.
  • Bilgisayar mühendisliğinde VLSI devre düzeni ve kayıt atama.
  • Hesaplamalı biyolojide protein yapısı tahmini ve genom birleştirme.
  • Kardinalite kısıtlamalı finansal portföy optimizasyonu.

Nasıl çalışır?

Nasıl çalışır?

1

Algoritma, öncelikle problemin gevşetilmiş bir sürümünü çözerek başlar — tipik olarak tamsayı kısıtlamalarını göz ardı eden LP gevşetmesi. Bu gevşetme, her uygun tamsayı çözümü gevşetmede de uygun olduğundan, gerçek optimal değer üzerinde bir üst sınır sağlar. Eğer gevşetilmiş çözüm tamsayı değerliyse, problem hemen çözülür.

Formül
\text{Solve LP relaxation: } z^* = \max\{\mathbf{c}^\top \mathbf{x} \mid A\mathbf{x} \leq \mathbf{b},\, \mathbf{x} \geq 0\}
2

Gevşetilmiş çözüm kesirli bir değişken içerdiğinde, algoritma değişkeni ya tabanına ya da tavanına zorlayan tamamlayıcı kısıtlamalar ekleyerek uygun bölgeyi böler. Her bölüm, arama ağacında yeni bir alt düğüm oluşturur, etkili bir şekilde bir alt problemi iki daha küçük alt probleme daha sıkı alanlarla böler.

Formül
\text{Select fractional variable } x_j \notin \mathbb{Z}\text{; create sub-problems: } x_j \leq \lfloor x_j^* \rfloor \text{ and } x_j \geq \lceil x_j^* \rceil
3

Her aktif düğüm kendi LP gevşetme sınırını alır. Sınırı, şimdiye kadar bulunan en iyi tamsayı çözümünü —incumbent olarak adlandırılır— aşmayan bir düğüm, daha iyi bir çözüm içeremez, bu nedenle budanır. Sıkı sınırlar kritiktir: sınır ne kadar sıkı olursa, o kadar az düğüm keşfedilmesi gerekir.

Formül
\text{Compute bound } UB_k \text{ for node } k\text{; prune if } UB_k \leq z_{\text{inc}}
4

Bir düğüm üç koşul altında sonlandırılır (kalıcı olarak kapatılır): gevşetmesi uygun değilse, sınırı mevcut en iyi çözümden (incumbent) daha iyi değilse veya gevşetilmiş çözümü zaten tamsayıya uygunsa. Son durumda, yeni çözüm iyileştirirse incumbent güncellenir. Algoritma, tüm düğümler sonlandırıldığında sona erer, bu noktada incumbent global optimumdur.

Formül
\text{Fathom node } k \text{ if infeasible, or } UB_k \leq z_{\text{inc}}, \text{ or } \mathbf{x}^*_k \in \mathbb{Z}^n\text{; update } z_{\text{inc}} \leftarrow \max(z_{\text{inc}}, z_k)

Sık yapılan hatalar

  • Dallanma değişkenini kötü seçmek (örneğin, her zaman ilk kesirli değişkende dallanmak) genellikle derin, dengesiz ağaçlara ve yavaş yakınsamaya yol açar.
  • Geçerli eşitsizlikleri (kesme düzlemleri) göz ardı etmek, gevşetme sınırlarını önemli ölçüde sıkılaştırma fırsatını kaçırmak anlamına gelir.
  • Alt optimallik farkıyla erken sonlandırma, bu şekilde rapor edilmediğinde, uygulayıcıları optimale yakın bir çözümü kesin olarak kabul etmeye yönlendirebilir.
  • Dal ve Sınır'ı doğrusal olmayan veya dışbükey olmayan gevşetmelere özel dışbükeyleştirme olmadan uygulamak geçersiz sınırlar ve yanlış sonuçlar verebilir.

Sık sorulan sorular

Dal ve Sınır, kapsamlı sayım (exhaustive enumeration) yönteminden nasıl farklıdır?

Kapsamlı sayım, her uygun tamsayı çözümünü açıkça değerlendirir, bu da büyük problemler için hesaplama açısından imkansızdır. Dal ve Sınır, arama ağacının her düğümünde gevşetme tabanlı üst sınırlar hesaplayarak ve sınırın zaten bulunan en iyi çözümü aşamayacağı durumlarda tüm alt ağaçları budayarak bunu önler. Pratikte, ağacın yalnızca küçük bir kısmı incelenir.

Dal ve Sınır'da LP gevşetmesinin rolü nedir?

LP gevşetmesi, tamsayı kısıtlamalarını kaldırarak problemi simpleks veya iç nokta yöntemiyle polinom zamanda çözülebilir hale getirir. Optimal değeri, ilgili tamsayı alt problemi için bir üst sınır görevi görür. Bu sınır sıkı olduğunda —gerçek tamsayı optimumuna yakın— daha az dalın keşfedilmesi gerekir. Genellikle geçerli eşitsizlikler eklenerek elde edilen daha sıkı gevşetmeler, genel algoritmayı önemli ölçüde hızlandırır.

Dal ve Sınır'ı genetik algoritmalar gibi bir meta-sezgisel yönteme ne zaman tercih etmeliyim?

Optimumluk sertifikası gerektirdiğinizde ve hesaplama süresini karşılayabildiğinizde Dal ve Sınır'ı seçin. İyi yapılandırılmış LP gevşetmelerine sahip orta büyüklükteki problemler için idealdir. Problem aşırı büyük olduğunda, faydalı bir gevşetmesi olmadığında veya optimale yakın bir çözümün kabul edilebilir olduğu sıkı bir zaman bütçesi dahilinde çözülmesi gerektiğinde meta-sezgisel yöntemler tercih edilir. Birçok uygulayıcı her ikisini birleştirir: erken sonlandırma fark toleransı ile Dal ve Sınır kullanın.

İlgili yöntemler

Kaynaklar

  1. Land, A. H., & Doig, A. G. (1960). An automatic method of solving discrete programming problems. Econometrica, 28(3), 497–520.

    DOI kaynağını aç
    Kopyalandı.