Dal ve Sınır

Dal ve sınır (branch and bound, B&B), karma tamsayılı programlama (MIP) ve birçok ayrık optimizasyon probleminin standart tam çözüm yöntemidir. Yöntemi Land ve Doig (1960) MIP için ortaya atmış, Little ve diğ. (1963) TSP'ye uygulamış, Dakin (1965) bütünsayı kısıtları üzerine dallandırma kuralını netleştirmiştir. Algoritma fizibıl bölgeyi rekürsif olarak alt-bölgelere ayırır (dallandırma — örneğin tamsayı değişkeni x için x ≤ ⌊x*⌋ ve x ≥ ⌈x*⌉ iki çocuk düğümü oluşturur), her düğümde **LP gevşemesi** çözerek alt-sınır (minimizasyonda) elde eder, mevcut en iyi tamsayı fizibıl çözüme (incumbent) göre üst-sınır tutar, alt-sınır ≥ incumbent olan düğümleri **budar** (prune by bound), tamsayı fizibıl çıkanları **kapatır** (prune by integrality), fizibıl olmayanları atar. Ağaç tükendiğinde incumbent globalin optimum çözümüdür. Branch-and-cut (Padberg ve Rinaldi 1991) B&B'yi cutting-plane ile birleştirir ve modern MIP çözücülerin omurgasıdır. Branch-and-price (Barnhart ve diğ. 1998) column generation ile birleştirir ve devasa formülasyonları çözer. Dallandırma stratejisi (most-fractional, strong branching, pseudocost branching), düğüm seçimi (best-first, depth-first, best-estimate) ve presolving B&B performansını dramatik etkiler. Wolsey (1998) *Integer Programming* ve Nemhauser ve Wolsey (1988) standart referanslardır. Modern MIP çözücüler 100M-değişken problemleri B&B + cut + heuristic kombinasyonuyla çözebilmektedir.