Branch and Bound

Branch and Bound เป็นอัลกอริทึมแบบแม่นตรง (exact algorithm) ที่เป็นระบบสำหรับการแก้ปัญหาการหาค่าเหมาะสมที่สุดเชิงการจัด (combinatorial optimization) และปัญหาจำนวนเต็ม (integer optimization) ซึ่งถูกนำเสนอโดย Ailsa Land และ Alison Doig ในปี 1960 อัลกอริทึมนี้จัดระเบียบปริภูมิการค้นหา (search space) ให้เป็นโครงสร้างแบบต้นไม้ (tree) ของปัญหาย่อย (subproblems) โดยใช้ค่าขอบบน (upper bounds) ที่ได้จากการผ่อนคลายเงื่อนไข (relaxation) เพื่อตัดกิ่งก้าน (prune branches) ที่ไม่สามารถปรับปรุงผลเฉลยที่ดีที่สุดที่ทราบได้ให้ดีขึ้น และรับประกันว่าจะได้ผลเฉลยจำนวนเต็มที่เหมาะสมที่สุดในระดับโลก (globally optimal integer solution) อัลกอริทึมนี้เป็นแกนหลักของตัวแก้ปัญหาการหาค่าเหมาะสมที่สุดเชิงจำนวนเต็มแบบผสม (mixed-integer programming solvers) ที่ทันสมัย ซึ่งใช้ในสาขาการวิจัยดำเนินงาน (operations research), โลจิสติกส์ (logistics), การจัดตารางเวลา (scheduling), และการออกแบบทางวิศวกรรม (engineering design)