1995-08-29
-----------------------
PROGRAM cdd README FILE
-----------------------
The program  cdd  is a C implementation of the Double Description 
Method of Motzkin et al. for generating all vertices (i.e. extreme points)
and extreme rays of a general convex polyhedron in R^d given by a system 
of linear inequalities:

   P = { x :  A  x  <=  b }

where  A  is an m x d real matrix and b is a real m dimensional vector.
The program can be used for the reverse operation (i.e. convex hull
computation) if one run cdd with "hull" option.  This means that 
one can move back and forth between an inequality representation 
and a generator (i.e. vertex and ray) representation of a polyhedron
with cdd.

The cdd package is in "tar"ed and "gzip"ed format with name
cdd-***.tar.gz, where *** is the version number.  The standard
anonymous ftp site for the package is

     ftp site : ifor13.ethz.ch (129.132.154.13)
     directory: pub/fukuda/cdd
     file name: cdd+-***.tar.gz

The old ftp site: ftp.efpl.ch (128.178.139.3) directory: incoming/dma
is no more valid and please do not use this site although
some of the old items are still there.

In order to unpack the package in a standard unix environment, type 
   
     % gunzip cdd-***.tar.gz
     % tar xvf cdd-***.tar

where *** must be replaced by the appropriate version number, and
% is a unix prompt. 

The package cdd consists of the following files which will be
placed in a newly created sub-directory cdd-*** :

     cdd.readme     This file itself

     cdd.c          C main source file
     cddarith.c     C subsource file 
     cddio.c        C subsource file  
     cdd.h          The header file for cdd.c
     cdddef.h       cdd definition file (whose two lines are to be edited by user)
     setoper.c      C library for set operation
     setoper.h      The header file for setoper.c 

     cddman.tex     Latex source file of cdd User Manual
     cddHISTORY     brief description of changes made at each updates
     ine            A subdirectory containing sample input files
     ext            A subdirectory containing sample output files
     COPYING        GNU GENERAL PUBLIC LICENSE

Before using the software, please read COPYING and
and read the manual cddman.tex.  

To compile the manual cddman.tex (in latex format) in a standard unix 
environment, run the following command twice: 

   % latex cddmax.tex

to get the dvi file, cddman.dvi.  On the printing or viewing commands
for cddman.dvi file, please ask a local system administrator.

For compilation of cdd, simply use the following:

   % gcc -o cdd cdd.c cddarith.c cddio.c setoper.c 

to get an executable file "cdd", where o is the lower letter "oh". 
For a faster code, compile them with an optimization option as 

   % gcc -o cdd -O cdd.c cddarith.c cddio.c setoper.c 

In above, gnu C compiler gcc can be replaced by the native C-compiler
cc of your system if cc supports the modern ANSI C. We have found that
some cc compilers (such as some C-compiler on SUN workstations)
do not support it.

There is a supplementary  C program, called domcheck,
written by Francois Margot of EPFL, which can be used with cdd 
to compute the orthogonal projection of a polyhedron onto
the subspace of any subset of variables.  The program domcheck
can be obtained from the same ftp site above. Note that
one needs the additional commercial program CPLEX to run domcheck.

The program cdd is free software, but if cdd turns out to be useful, 
please kindly send to me (at the address below) a note or a paper mentioning 
for what purpose and how cdd has been used. The most powerful support 
for free software development is user's appreciation.   

For more information, contact
   Komei Fukuda
   fukuda@ifor.math.ethz.ch
   Institut fur Operations Research
   ETH Zentrum, CH-8092 Zurich, Switzerland
   fax +41-1-632 1025   tel +41-1-632 4023 or 4028

// END of cdd.readme