A new node selection strategy in the branch-and-bound procedure

This paper proposes a new node selection strategy, known as the locally best bound rule, and incorporates it into the Balas’ algorithm, a well-known branch-and-bound algorithm for solving pure binary integer programming problems. Computational results show that the new strategy requires not only much less amount of core storage than the best bound rule but also less amount of computation in most cases. Based on a detailed analysis of the computational results, it is believed that the superiority of the locally best bound rule can be expected in many other branch-and-bound algorithms.