Branch and Bound
Ayrıca şöyle bilinir: B&B, Land-Doig Algorithm, Implicit Enumeration, Dal ve Sınır
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. Dallara Ayırma ve Sınırlama 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.
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
Tamsayı ve kombinatoryal programlar için küresel optimalliği garanti eder.
Güçlü yönler & sınırlılıklar
- Sınır tabanlı budama yoluyla arama süresini dramatik bir şekilde azaltır — genellikle tam enumerasyon ağacının yalnızca küçük bir kısmı keşfedilir.
- Esnektir: daha fazla verimlilik için kesme düzlemleri (dallara ayırma-kesme) veya sezgisel sınırlar (dallara ayırma-fiyatlandırma) içerebilir.
- Olgun ticari çözücülerde (CPLEX, Gurobi) ve açık kaynaklı araçlarda (GLPK, CBC) yaygın olarak uygulanmıştır.
- 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 çözülebilir 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.
- 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.
SSS
Tümel 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. Dallara Ayırma ve Sınırlama, 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.
Dallara Ayırma ve Sınırlama'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.
Dallara Ayırma ve Sınırlama'yı genetik algoritmalar gibi bir meta-sezgisel yönteme ne zaman tercih etmeliyim?
Optimumluk sertifikası gerektirdiğinizde ve hesaplama süresini karşılayabildiğinizde Dallara Ayırma ve Sınırlama'yı 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 yakın-optimal 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 Dallara Ayırma ve Sınırlama kullanın.
Dallara Ayırma ve Sınırlama, Python'da `scipy.optimize.milp`, CBC ile `PuLP` ve `cvxpy` aracılığıyla; R'de `Rglpk` ve `ompr` paketleri aracılığıyla; ve Gurobi ve IBM CPLEX gibi ticari çözücülerde ilgili Python ve Java API'leri aracılığıyla yerel olarak mevcuttur.
Kaynaklar
- Land, A. H., & Doig, A. G. (1960). An automatic method of solving discrete programming problems. Econometrica, 28(3), 497–520. DOI: 10.2307/1910129 ↗
Bu sayfayı kaynak gösterin
ScholarGate. (2026, June 2). Branch and Bound. ScholarGate. https://scholargate.app/tr/optimization/branch-and-bound
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
- Tamsayı ProgramlamaOptimizasyon↔ karşılaştır