A New Method for Constructing the Search Tree in Branch and Bound Algorithm
Abolfazl Jalilvand, Sohrab Khanmohammadi · 2005
The branch and bound (B&B) algorithm is one of the common-used methods for solving the discrete optimization problems. In this method the optimal solution will be found by searching the space of solutions. The search space of most B&B algorithms is inherently large and computationally complex. Hence constructing whole of the search space in applying the B&B algorithm needs a large memory size. This paper presents a new method to construct search tree in B&B algorithm gradually. In this method the search tree is formed step by step. Each node is constructed when it must be tested and there isn't need to construct the whole search tree at once. This method needs a minimum size of memory. Two lemmas are proposed and proved related to this new method