Sözlük · approach
Branch-and-Cut
Dal-sınır (branch-and-bound) ile kesme-düzlemi (cutting plane) yöntemlerini birleştiren exact MIP çözüm çerçevesi — arama ağacının her düğümünde geçerli eşitsizlikler (kesimler) LP gevşemesini sıkıştırır, sonra dallandırma yapılır.
Branch and CutDal-ve-KesKesme-Düzlemi Dal-SınırB&C
Branch-and-cut, modern her ticari ve açık-kaynak MIP çözücüsünün temelinde yatan exact karma-tamsayı programlama (MIP) çözüm çerçevesidir. İki fikri birleştirir: (a) **branch-and-bound** — tamsayı problemi değişken-dallandırması ile küçük alt-problemlere böl, her düğümde LP gevşemesini çöz, LP-sınırı mevcut en iyi fizibıl çözümden kötü olan alt-ağaçları kes; (b) **kesme-düzlemleri** — dallandırmadan önce her tamsayı fizibıl çözüm tarafından sağlanan ama mevcut kesirli LP optimumu'nu kesip atan geçerli eşitsizlikler (kesimler) ekle; bu LP gevşemesini sıkıştırır ve bound aralığını daraltır. Yaklaşım Dantzig, Fulkerson ve Johnson (1954) tarafından Travelling Salesman Problem (TSP) üzerinde ortaya konuldu — alt-tur eliminasyonu kesimlerini dal-sınır araması içinde kullanıp 49-şehirli nüshayı exact optimum'a çözdüler. Padberg ve Rinaldi (1991) çerçeveyi, ihlal edilmiş kesimleri uçuş halinde tespit eden ayırma rutinleri ile genelleştirdi. Bugün branch-and-cut, TSP, VRP, çizelgeleme, tesis yerleşim ve onlarca diğer kombinatoryel optimizasyon problemi için varsayılan exact yöntemdir; TSP üzerinde raporlanan çözücü performansı 85K+ düğümü aşmıştır (Applegate, Bixby, Chvátal ve Cook 2006). Pratikte kullanılan kesimler: subtour-elimination, comb eşitsizlikleri, clique kesimleri, Gomory kesimleri, karma-tamsayı-yuvarlama kesimleri, lift-and-project kesimleri.
Örnek
Bir saha hizmet rotası için 200-durak'lı TSP modern branch-and-cut MIP çözücüsünde 4 dakikada exact optimum'a çözülür; 2-opt sezgisel 2 saniyede %12 daha kötü tur verir.