Improving the performance of enumerative search methods-Part II: Computational experiments

Generally, branch and bound algorithms typically use mechanistic search strategies and generally do not fully exploit ‘local’ information inherent in problem structures; that is, specific problem-domain knowledge. Some exceptions are found. Incorporating intelligence in branch and bound algorithms has been suggested by Glover, but not studied in a rigorous experimental framework. The authors use the mean tardiness job sequencing problem to explore these issues. This paper is divided into two Parts. In Part I, the authors provided the intuitive motivation for this investigation and an experimental framework. In Part II, they present detailed computational results and statistical analysis. The results indicate that branch and bound algorithms can be enhanced significantly by exploiting local knowledge of problem structure and more judicious search strategies.