Polyhedral Computation Codes

• cddlib, cdd and cdd+ [Fuk02] (C and C++ implementations of the double description method [MRTT53]).

  Comments: Floating and exact arithmetic. Efficient for highly degenerate cases. The exact version cddr+ is much slower. It can remove redundancies from input data using a built-in LP code. cddlib is a C-library with basic polyhedral conversion functions and LP solvers. cddlib can be compiled with both GMP rational (mpq) and floating point arithmetic.

• lrs [Avi] (C implementation of the reverse search algorithm [AF92]). A parallel version prs has been developed by A. Marzetta, see [BMFN96].

  Comments: Exact arithmetic only, efficient for nondegenerate cases. Uses a little memory and perhaps the only available code which can deal with problems generating huge output (say, one million vertices/facets).

• pd [Mar97] (C implementation of the primal-dual algorithm [BFM97]).

  Comments: Exact arithmetic only, efficient for dually nondegenerate cases.

• qhull [BDH96,BDH03] (C implementation of the beneath-beyond method, see [Ede87,Mul94], which is the dual of the dd method).

  Comments: Floating arithmetic only but handles numerical problems well. Highly efficient for nondegenerate cases. User can call it as a C-libary.

• porta [CL97] (C implementation of the Fourier-Motzkin elimination method [Zie94]).

  Comments: Efficient for combinatorial (e.g. 0-1) polytopes. Guarantees correct numerical results as long as double precision integer arithmetic does not overflow. It can list all integer solutions in a polytope.

• polymake [GJ99] (computational environment for the algorithmic treatment of polytopes and polyhedra).

  One can generate convex polytopes and do various computations with convex polyhedra. It uses cdd+/porta/lrs for representation conversions. It is extendable by writing own "rules" to generate new structures/data associated with polyhedra.

• zeRone [Lüb99] (C implementation of the backtrack vertex enumeration algorithm for 0-1 H-polytopes [BL98].

  Comments: In general, the straightforward backtrack algorithm for the vertex enumeration problem must solve NP-complete decision problems, as it was shown in [FLM97]. The situation is different for 0-1 polytopes and the problem is strongly polynomially solvable. The code can generate all 0-1 points in a general H-polytope. It relies on the commercial LP solver CPLEX.

• Pointers to many other programs in geometric computations are stored in [Ame,Eri].

• For linear programming, one should check the Linear Programming FAQ at [FG]. It lists both public (open source) and commercial codes.