AN IMPLEMENTATION OF A PARALLEL GENERALIZED BRANCH AND BOUND TEMPLATE
Authors:
- 30 September 2007
- journal article
- Published by Vilnius Gediminas Technical University in Mathematical Modelling and Analysis
- Vol. 12 (3)
Abstract
Branch and bound (BnB) is a general algorithm to solve optimization problems. We present a template implementation of the BnB paradigm. A BnB template is implemented using C++ object oriented paradigm. MPI is used for underlying communications. A paradigm of domain decomposition (data parallelization) is used to construct a parallel algorithm. To obtain a better load balancing, the BnB template has the load balancing module that allows the redistribution of search spaces among the processors at run time. A parallel version of user's algorithm is obtained automatically. A new derivative-free global optimization algorithm is proposed for solving nonlinear global optimization problems. It is based on the BnB algorithm and its implementation is done by using the developed BnB algorithm template library. The robustness of the new algorithm is demonstrated by solving a selection of test problems.Keywords
This publication has 3 references indexed in Scilit:
- Revisiting Asynchronous Parallel Pattern Search for Nonlinear OptimizationSIAM Journal on Optimization, 2005
- From Design Patterns to Parallel Architectural SkeletonsJournal of Parallel and Distributed Computing, 2002
- Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods1994