1997-12-01
--------------------------------------
PROGRAM cdd (version 0.61) 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).  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 version 0.61 adopts the updated Polyhedra format with
"H-representation" and "V-represetation" statements.  The linear
programming library dplex has been updated and debugged.  The library
has a new function dp_FindInteriorPoint to return an interior point
of a convex polyhedron.

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 : 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. 

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          header file for cdd.c
     cdddef.h       cdd definition file (whose two lines are to be edited by user)
     dplex.c        dual simplex library
     dplex.h        header file for dplex
     dplexdef.h     additional header file for dplex
     dplex_test.c   sample main program for dplex
     setoper.c      C library for set operation
     setoper.h      header file for setoper.c 
     cddman.tex     Latex source file of cdd User Manual
     Makefile       GNU make file
     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 latex2e 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:

   % make all

which will generate two executables, cdd and dplex_test.
If this fails, modify Makefile, or one might want to try:

   % gcc -O -I. -o cdd cdd.c cddarith.c cddio.c dplex.c setoper.c 
   % gcc -O -I. -o dplex_test dplex_test.c dplex.c setoper.c 

to get an executable files "cdd" and "dplex_test".

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.

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.

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-1015 Lausanne, Switzerland
   homepage: http://www.ifor.math.ethz.ch/staff/fukuda/fukuda.html

// END of cdd.readme