Cabang dan Batas

Branch and Bound adalah algoritma eksak sistematis untuk masalah optimasi kombinatorial dan integer, yang diperkenalkan oleh Ailsa Land dan Alison Doig pada tahun 1960. Algoritma ini mengorganisasi ruang pencarian sebagai pohon submasalah, menggunakan batas atas yang diturunkan dari relaksasi untuk memangkas cabang yang tidak dapat meningkatkan solusi terbaik yang diketahui, dan menjamin penemuan solusi integer optimal secara global. Algoritma ini merupakan tulang punggung pemecah masalah pemrograman campuran integer modern yang digunakan dalam riset operasi, logistik, penjadwalan, dan desain teknik.