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 further contains 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 and the enumeration of the vertices of complex high-dimensional polytopes.
In this talk, we present ZRAM, its architecture and some of its applications (quadratic assignment problem, vertex and facet enumeration, Euclidean spanning trees).
More information is available at http://wwwjn.inf.ethz.ch/ambros/zram/zram.html.