A New Method for Constructing the Search Tree in Branch and Bound Algorithm

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