Keywords: branch and bound method, size optimization, benchmarks, global optima, mixed-integer linear problem, big-M problem, parallel computing.

Recently, many heuristic and metaheuristic algorithms have been developed and tested on various benchmarks in order to assess their performance [1]. To compare distinct optimization methods, it is appropriate to know the global optima of benchmarks in a reliable way. This paper presents our new formulation of a classical branch and bound method to find the most efficient way how to gain global optima of larger structures.

A branch and bound method is based on a division of the main problem to several subproblems, so-called branches. To estimate which branches are to be evaluated, an existence of the lower and upper bounds is assumed to restrict the searched space. Since the constraints for the sizing optimization problem are more computationally demanding than the value of the objective function, they are calculated only for solutions that lie between bounds. It is thus advantageous to bring the bounds closer based on the objective function's values already obtained.

In the previous procedure based on branch and bound principles and an enumeration [2], the branching was done at an assignment of areas to the trusses, i.e. we have been solving the original problem in the integer manner. However, the classical branch and bound method (BB) requires a model with convex objectives and constraints, which is not the case of the above mentioned solution and a reason why the enumeration was used. To convert the non-convex problem to the convex one, a relaxation of some variables is therefore necessary. The original design variables (cross-section areas on truss-bars) are converted to the binary design variables (with the meaning whether cross-section area is present for the respective truss-bar or not) and some additional variables (stresses and displacements) are included with them. This problem is relaxed and gives the lower bound for the BB.

Particularly, we follow the procedure for topology optimization presented in [3]. Some modifications were needed to transform the topology optimization into sizing one. Next, a parallel version of the classical BB algorithm was implemented, see e.g. [4], where the upgrades of the lower and upper bounds are broadcasted among individual processes. This algorithm was used to compute the global optimum for our 5-bar truss as well as for the frequently used 25-bar truss benchmark and the global optima were obtained.

1

A.C.C. Lemonge, H.J.C. Barbosa, "An adaptive penalty scheme for genetic algorithms in structural optimization", International Journal for Numerical Methods in Engineering, 59(5):703-736, 2004.

2

A. Pospíšilová, M. Lepš, "Global optima for size optimization benchmarks by branch and bound principles", Acta Polytechnica, 52(6):50-57, 2012.

3

M. H. Rasmussen, M. Stolpe, "Global optimization of discrete truss topology design problems using a parallel cut-and-branch method", Computers and Structures, 86:1527-1538, 2008.

4

W. Zhang, "Parallel multi-objective branch and bound", Master's thesis, Technical University of Denmark, 2008.

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description
purchase this book (price £40 +P&P)