Share:


An implementation of a parallel generalized branch and bound template

    Milda Baravykaitė Affiliation
    ; Raimondas Čiegis Affiliation

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

Keyword : 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
Published in Issue
Sep 30, 2007
Abstract Views
486
PDF Downloads
351
Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.