1997-11-30
---------------------------------------
PROGRAM cdd+ (version 0.75) 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+.  Also, cdd+ can solve a linear programming problem, i.e.
a problem of maximizing and minimizing a linear function over P.

The program cdd+ is a C++ version of the ANSI C
program cdd basically for the same purpose.  The main difference is that 
it can be compiled for both rational (exact) arithmetic and 
floating point arithmetic. (Note that cdd runs on floating
arithmetic only.)  Since cdd+ uses GNU g++ library, in particular 
Rational library, one needs a recent (2.6.0 or higher) gcc compiler
and g++-lib.  The program seems to be 
stable when compiled with gcc-2.6.3 and libg++-2.6.2, or
more recent. 

What's new in Version 0.75?
The version 0.75 is a maintenance release which accepts
an updated Polyhedra format with "H-representation" and
"V-representation" statements.  Also, we added three additional
options "zero_tolerance", "round_output_off" and 
"output_digits".  The first one is to set a zero tolerance 
of floating-point computation, and the latter ones are to 
control the format of output numbers.
See cddman.tex for details.

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

     ftp site : ftp.ifor.math.ethz.ch
     directory: pub/fukuda/cdd
     file name: cdd+-***.tar.gz

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. If you have GNU gzcat command, one can simply
unpack the package at once by

     % gzcat cdd+-***.tar.gz | tar xvf - 

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++ main arithmetic code 
     cddpivot.C    C++ pivot operation arithmetic code 
     cddio.C       C++ IO code 
     cddrevs.C     C++ reverse search code 
     cdd.h         The header file for cdd.C
     cdddef.h      cdd+ definition file (whose two lines are to be edited by user)
     cddtype.h     cdd+ arithmetic type definition file
     cddrevs.h     The header file for cddrevs.C
     setoper.C     C++ library for set operation
     setoper.h     The header file for setoper.C 

     cddman.tex    Latex source file of cdd+ User Manual
     cddman.bbl  & bibliography file of cdd+ Reference Manual\\
     cddHISTORY    brief description of changes made at each updates
     ine           A subdirectory containing sample inequality input files
     ext           A subdirectory containing sample points/rays input 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 latex2e format) in a standard unix 
environment, run the following command twice: 

   % latex cddman.tex

to get the dvi file, cddman.dvi.  On the printing or viewing commands
for cddman.dvi file, please ask a local system administrator.
An html version of cddman can be created with latex2html translator
by Nikos Drakos.  Use Version 96.1 or later.

For compilation of cdd+, edit Makefile according to the local
setup of a GNU gcc compiler and g++-library, and type

   % make all

which creates two executables, cddr+ and cddf+.  The executable
cddr+ computes with rational (exact arithmetic) and cddf+ computes
with floating-point arithmetic.  If you want to create only one of
them, use "make cddf+" or "make cddr+".  Once these executables are 
created one might want to remove all object files *.o by

   % rm *.o

There is a supplementary  C program, called domcheck,
written by Francois Margot, 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.
Also it runs on floating-point arithmetic only.

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
   Zurich  :IFOR, ETH Zentrum, CH-8092 Zurich, Switzerland  
   Lausanne:DMA, EPFL, Ch-1007 Lausanne, Switzerland
   homepage: http://www.ifor.math.ethz.ch/staff/fukuda/fukuda.html

// END of cdd+.readme