Design and use of the CPAN branch and bound for the solution of the travelling salesman problem (TSP)

• Main Authors: Tunon, M.I.C., Lopez, M.R.
• Format: Conference Proceeding
• Language: English
• Subjects: Algorithm design and analysis; Binary trees; Cost function; Design optimization; Libraries; Parallel programming; Pipelines; Space exploration; Traveling salesman problems; Yarn
• DOI: 10.1109/CONIEL.2005.33

This article presents the design of a high level parallel composition or CPAN (according to its Spanish acronym) that implements a parallelization of the algorithmic design technique named branch and bound and uses it to solve the travelling salesman problem (TSP), within a methodological infrastructure made up of an environment of parallel objects, an approach to structured parallel programming and the object-orientation paradigm. A CPAN is defined as the composition of a set of parallel objects of three types: one object manager, the stages and the collector objects. By following this idea, the branch and bound design technique implemented as an algorithmic parallel pattern of communication among processes and based on the model of the CPAN is shown. Thus, in this work, the CPAN branch and bound is added as a new pattern to the library of classes already proposed in Rossainz et al. (2004), which was initially constituted by the CPAN farm, pipe and treeDV that represent, respectively, the patterns of communication farm, pipeline and binary tree, the latter one implementing the design technique known as divide and conquer. As the programming environment used to derive the proposed CPAN, we use C++ and the POSIX standard for thread programming.