ZRAM
A portable library of parallel search algorithms and data structures
A note from the maintainer
ZRAM was written by Ambros Marzetta as part of his Ph.D. at ETH Zuerich.
Since then I have done some maintenence in order to use it in my own projects. Most of the code remains Ambros's
 David Bremner
ZRAM is a library of parallel search algorithms and the corresponding data structures. The implementation is applicationindependent and machineindependent. The interface is userfriendly and lets nonspecialists use the power of parallel computers. ZRAM has led to the solution of previously unsolved QAP and vertex enumeration instances.
The library can be used in combinatorial optimization, enumeration, heuristic search and other areas. It is written in ANSI C, and its source code is available here.
Architecture
[[!img Error: Image::Magick is not installed]]
Implemented parallel search algorithms and some applications using them:
Branch and bound
Quadratic Assignment Problem
Minimum vertex cover
Traveling Salesman Problem (TSP)

Vertex enumeration of convex polyhedra / convex hull
Enumeration of connected induced subgraphs (PostScript example)
Enumeration of polyominoes
Enumeration of Euclidean spanning trees (fivepoint example in Encapsulated PostScript)
Enumeration of k best Euclidean spanning trees (48 best spanning trees of an 8point set in PDF)
Enumeration of fat and skinny trees.
Backtracking
Parallel computers used:
Workstation networks using MPI
Intel Paragon
NEC Cenju3
Sun Ultra
(Only MPI is currently tested).
Literature
Ambros Marzetta, ZRAM: A Library of Parallel Search Algorithms and Its Use in Enumeration and Combinatorial Optimization. PhD thesis Nr. 12699, ETH Zürich, 1998 (119 pages; abstract, Kurzfassung gzipped PostScript, PostScript, Acrobat PDF).
Adrian Brüngger, Ambros Marzetta, Jens Clausen and Michael Perregaard, Solving LargeScale QAP Problems in Parallel with the Search Library ZRAM, Journal of Parallel and Distributed Computing 50 (1998), 157169. (14 pages; PostScript, gzipped PostScript, Acrobat PDF)
Adrian Brüngger, Ambros Marzetta, Komei Fukuda and Jürg Nievergelt, The Parallel Search Bench ZRAM and its Applications, Annals of Operations Research, 90:4563, 1999.
Adrian Brüngger, Ambros Marzetta, Jens Clausen and Michael Perregaard, Joining Forces in Solving LargeScale Quadratic Assignment Problems in Parallel, Proceedings of the 11th International Parallel Processing Symposium IPPS 97. (10 pages)
Adrian Brüngger and Ambros Marzetta, The Parallel Search Bench ZRAM and its Applications, CrosSCutS December 1996. (4 pages; gzipped PostScript)