Ambros Marzetta. ZRAM: A Library of Parallel Search Algorithms and Its Use in Enumeration and Combinatorial Optimization. PhD thesis Nr. 12699, ETH Zürich. Kurzfassung

Abstract

ZRAM is a software library which renders the power of parallel computers usable for combinatorial optimization and enumeration. It provides a set of parallel search engines for branch-and-bound, reverse search, backtracking and tree-size estimation. These search engines hide the complexity of parallelism from the application programmer. ZRAM contains the first parallel implementation of the reverse-search algorithm and the first parallel branch-and-bound engine that can be restarted at checkpoints. It is the first search library containing a tree-size estimation tool, which proved to be valuable in allocating the limited CPU resources to the most promising problem instances. The combination of these elements, together with the efficiency of the implementation, allowed us to solve large enumeration and combinatorial optimization problems. These benchmarks include quadratic assignment instances which were previously unsolved and the enumeration of the vertices of complex high-dimensional polytopes. ZRAM has proved its flexibility during the development of a wide range of applications (e.g., quadratic assignment problem, vertex and facet enumeration, hyperplane arrangements, 15-puzzle, Euclidean spanning trees, connected induced subgraphs). Some of its users had little or no experience in parallel programming and got access to parallel computers only through ZRAM. The work on ZRAM has clarified what properties we require of a parallel search library and demonstrates that a four-layered structure (applications, search engines, common services, host systems) is a suitable architecture.