2003-08-19
---------------------------------------
PROGRAM cdd+ (version 0.77) README FILE
---------------------------------------
1. 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.) 

2. What's new in Version 0.77?

This version is a minor revision over 076.  The main purpose was
to revise the programs so that they can be complied with modern
gcc compilers, like gcc 3.1.*.   Several people helped me create
this version, in particular Francois Margot (Univ. Kentucky and
IBM Watson, USA) provided a fix for 0.76a1.

Since there are no new functions added to this version,
the manual (cddman.tex) has not been rewritten and it is
for the previous version 0.76.

It now assumes that GNU GMP (http://www.swox.com/gmp/ )
has been installed before cdd+ is complied.  Please ask your local
system administrator whether GMP is stalled, and where it is installed. 
You need to edit makefile according to the local environment.

Please note that the development of cdd* has been shifted to its
C-library version, cddlib.  It is more powerful because it can be called
from your own programs, and it does not assume anything on the data.  It
can deal (in principle) any input.  If you think that cdd+ does not
work as you expected, please try the most recent version of cddlib.
In particular, the LP solver in cdd+ is not reliable as the one in cddlib.


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

     web site : http://www.cs.mcgill.ca/~fukuda/soft/cdd_home/cdd.html 

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+-*** :

     README.cdd+   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
     HISTORY.cdd   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

     Integer.cc, Rational.cc, gmp_init.cc
                   Polymake's GMP wrappers in C++

     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@cs.mcgill.ca
   homepage: http://www.cs.mcgill.ca/~fukuda

// END of cdd+.readme