Branch and Bound Algorithm

A Branch and Bound Algorithm is a search algorithm strategy.

• Context:
  • It is a form of Backtracking Algorithm.
  • It can be an Integer Linear Programming Algorithm.
• See: Scheduling Task.

---

---

References

2009

• http://en.wikipedia.org/wiki/Branch_and_bound
  • Branch and bound (BB) is a general algorithm for finding optimal solutions of various optimization problems, especially in discrete and combinatorial optimization. It consists of a systematic enumeration of all candidate solutions, where large subsets of fruitless candidates are discarded en masse, by using upper and lower estimated bounds of the quantity being optimized.
  • The method was first proposed by A. H. Land and A. G. Doig in 1960 for linear programming.

1977

• (Narendra & Fukunaga, 1977) ⇒ P. M. Narendra, and K. Fukunaga. (1977). “A Branch and Bound Algorithm for Feature Subset Selection.” In: IEEE Trans. Comput. 26(9). doi:10.1109/TC.1977.1674939

1960

• (Land & Doig, 1960) ⇒ A. H. Land and A. G. Doig. (1960). “An Automatic Method of Solving Discrete Programming Problems.” In: Econometrica, 28(3). http://www.jstor.org/stable/1910129

---