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.