-
Notifications
You must be signed in to change notification settings - Fork 2
/
cdd.readme
111 lines (85 loc) · 4.28 KB
/
cdd.readme
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
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
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