Mts: a light framework for parallelizing tree search codes. (4th May 2021)

• Record Type: Journal Article
• Authors: Avis, David; Jordan, Charles
• Is Part Of: Optimization methods and software. Volume 36:Number 2/3(2021)
• Page Start: 279
• Page End: 300
• Publication Date: 2021-05-04
• Subjects: Reverse search -- parallel processing -- topological sorts -- spanning trees -- triangulations -- satisfiability testing; 90C05; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2019.1692344
• Languages: English
• ISSNs: 1055-6788

Abstract

Abstract : We describe mts, a generic framework for parallelizing certain types of tree search programmes including reverse search, backtracking, branch and bound and satisfiability testing. It abstracts and generalizes the ideas used in parallelizing lrs, a reverse search code for vertex enumeration. mts supports sharing information between processes which is important for applications such as satisfiability testing and branch-and-bound. No parallelization is implemented in the legacy single processor programmes minimizing the changes needed and simplifying debugging. mts is written in C, uses MPI for parallelization and can be used on a network of computers. We give four examples of reverse search codes parallelized by using mts : topological sorts, spanning trees, triangulations and Galton-Watson trees. We also give a parallelization of two codes for satisfiability testing. We give experimental results comparing the parallel codes with other codes for the same problems.