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 application-independent and machine-independent. The interface is user-friendly and lets non-specialists 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

Implemented parallel search algorithms and some applications using them:

• Branch and bound

  • Quadratic Assignment Problem

  • Minimum vertex cover

  • Traveling Salesman Problem (TSP)

• Reverse search

  • Vertex enumeration of convex polyhedra / convex hull

  • Enumeration of connected induced subgraphs (PostScript example)

  • Enumeration of polyominoes

  • Enumeration of Euclidean spanning trees (five-point example in Encapsulated PostScript)

  • Enumeration of k best Euclidean spanning trees (48 best spanning trees of an 8-point set in PDF)

  • Enumeration of fat and skinny trees.

• Backtracking

  • N-queens problem (the standard backtrack example) (7 queens and 8 queens PostScript)

  • Enumeration of all partitions of a set

Parallel computers used:

• Workstation networks using MPI

• Intel Paragon

• NEC Cenju-3

• GigaBooster

• 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 Large-Scale QAP Problems in Parallel with the Search Library ZRAM, Journal of Parallel and Distributed Computing 50 (1998), 157-169. (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:45-63, 1999.

• Adrian Brüngger, Ambros Marzetta, Jens Clausen and Michael Perregaard, Joining Forces in Solving Large-Scale 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)