Enhancing Branch-and-Bound Method for Structural Optimization

Abstract

The branch-and-bound method was originally developed to cope with difficulties caused by discontinuous design variables in linear programming. When the branch-and-bound method is applied to solve nonlinear programming (NLP) problems with a large number of mixed discontinuous and continuous design variables, the slow rate of convergence becomes a major drawback of the method. In this study, a number of enhancements are proposed to speed up the rate of convergence of the conventional branch-and-bound algorithm. Three NLP in the form of truss-design examples are tested to compare the capabilities and efficiency of the proposed enhancements. It is shown that of the five criteria for arranging the order in which the design variables are branched, the criterion of maximum cost difference dramatically reduces the number of branch nodes, thereby reducing the total number of continuous-optimization runs executed. Moreover, neighboring search, a branching procedure restricted in the neighborhood of the continuous optimum, is proven to be effective in speeding up the convergence. Investigation also shows that branching several design variables simultaneously is not as efficient as sequentially branching one variable at a time. The proposed enhancements are incorporated along with a sequential quadratic programming algorithm into a software package that is shown to be very useful in the optimal design of engineering structures.