An implementation of a parallel generalized branch and bound template

    Milda Baravykaitė Info
    Raimondas Čiegis Info

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.

First Published Online: 14 Oct 2010

Keywords:

branch and bound, template programming, parallel algorithms

How to Cite

Baravykaitė, M., & Čiegis, R. (2007). An implementation of a parallel generalized branch and bound template. Mathematical Modelling and Analysis, 12(3), 277-289. https://doi.org/10.3846/1392-6292.2007.12.277-289

Share

Published in Issue
September 30, 2007
Abstract Views
575

View article in other formats

CrossMark check

CrossMark logo

Published

2007-09-30

Issue

Section

Articles

How to Cite

Baravykaitė, M., & Čiegis, R. (2007). An implementation of a parallel generalized branch and bound template. Mathematical Modelling and Analysis, 12(3), 277-289. https://doi.org/10.3846/1392-6292.2007.12.277-289

Share