Introduction

The program cddlib is an efficient implementation [12] of the double description Method [14] for generating all vertices (i.e. extreme points) and extreme rays of a general convex polyhedron given by a system of linear inequalities:

$$P = \{ x=(x_1, x_2, \ldots, x_d)^T \in R^{d}: b - A x \ge 0 \}$$

where $A$ is a given $m \times d$ real matrix and $b$ is a given real $m$-vector. In the mathematical language, the computation is the transformation of an H-representation of a convex polytope to an V-representation.

cddlib is a C-library version of the previously released C-code cdd/cdd+. In order to make this library version, a large part of the cdd source (Version 0.61) has been rewritten. This library version is more flexible since it can be called from other programs in C/C++. Unlike cdd/cdd+, cddlib can handle any general input and is more general. Furtthermore, additional functions have been written to extend its functionality.

One useful feature of cddlib/cdd/cdd+ is its capability of handling the dual (reverse) problem without any transformation of data. The dual transformation problem of a V-representation to a minimal H-representation and is often called the (convex) hull problem. More explicitly, is to obtain a linear inequality representation of a convex polyhedron given as the Minkowski sum of the convex hull of a finite set of points and the nonnegative hull of a finite set of points in $R^{d}$:

$$P = conv(v_1,\ldots,v_n) + nonneg(r_{n+1},\ldots,r_{n+s}),$$

where the Minkowski sum of two subsets $S$ and $T$ of $R^{d}$ is defined as

$$S + T = \{ s + t \; \vert s \in S \mbox{ and } t \in T \}.$$

As we see in this manual, the computation can be done in straightforward manner. Unlike the earlier versions of cdd/cdd+ that assume certain regularity conditions for input, cddlib is designed to do a correct transformation for any general input. The user must be aware of the fact that in certain cases the transformation is not unique and there are polyhedra with infinitely many representations. For example, a line segment (1-dimensional polytope) in $R^3$ has infinitely many minimal H-representations, and a halfspace in the same space has infinitely many minimal V-representations. cddlib generates merely one minimal representation.

cddlib comes with an LP code to solve the general linear programming (LP) problem to maximize (or minimize) a linear function over polyhedron $P$. It is useful mainly for solving dense LP's with large $m$ (say, up to few hundred thousands) and small $d$ (say, up to 100). It implements a revised dual simplex method that updates $(d+1)\times (d+1)$ matrix for a pivot operation.

The program cddlib has an I/O routines that read and write files in Polyhedra format which was defined by David Avis and the author in 1993, and has been updated in 1997. The program called lrs [2] developed by David Avis is a C-implementation of the reverse search algorithm [4] for the same enumeration purpose, and it conforms to Polyhedra format as well. Hopefully, this compatibility of the two programs enables users to use both programs for the same input files and to choose whichever is useful for their purposes. From our experiences with relatively large problems, the two methods are both useful and perhaps complementary to each other. In general, the program cddlib tends to be efficient for highly degenerate inputs and the program rs tends to be efficient for nondegenerate or slightly degenerate problems.

Although the program can be used for nondegenerate inputs, it might not be very efficient. For nondegenerate inputs, other available programs, such as the reverse search code lrs or qhull (developed by the Geometry Center), might be more efficient. See Section 8 for pointers to these codes. The paper [3] contains many interesting results on polyhedral computation and experimental results on cdd+, lrs, qhull and porta.

This program can be distributed freely under the GNU GENERAL PUBLIC LICENSE. Please read the file COPYING carefully before using.

I will not take any responsibility of any problems you might have with this program. But I will be glad to receive bug reports or suggestions at the e-mail addresses above. If cddlib turns out to be useful, please kindly inform me of what purposes cdd has been used for. I will be happy to include a list of applications in future distribution if I receive enough replies. The most powerful support for free software development is user's appreciation and collaboration.