-
Notifications
You must be signed in to change notification settings - Fork 2
/
cddman.tex
1210 lines (1059 loc) · 48.7 KB
/
cddman.tex
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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
% The name of this file: cddman.tex
% written by by Komei Fukuda
% December 14, 1993
% Revised March 17, 1999
%
\documentclass[11pt]{article}
\usepackage{html}
\renewcommand{\baselinestretch}{1}
\renewcommand{\arraystretch}{1}
\setlength{\oddsidemargin}{8mm}
\setlength{\textwidth}{16cm}
\setlength{\topmargin}{-15mm}
\setlength{\textheight}{235mm}
%\setlength{\headsep}{0in}
%\setlength{\headheight}{0pt}
\pagestyle{plain}
\begin{document}
\title{cdd/cdd+ Reference Manual}
\author{
Komei Fukuda \\
Institute for Operations Research\\
ETH-Zentrum, CH-8092 Zurich, Switzerland\\
fukuda@ifor.math.ethz.ch \\and\\
Department of Mathematics\\
ETFL, CH-1015 Lausanne, Switzerland}
\date{ (cdd ver. 0.61 and cdd+ ver. 0.76, March 17, 1999)}
\maketitle
\section{What's new?}
Thanks to TU-Berlin's Polymake Team, cdd+ now runs with GNU's
GMP rational library as well as with the GNU g++ Rational library.
In particular, Polymake Team (Ewgenij Gawrilow and Michael Joswig)
wrote C++ wrappers "gmp\_integer.cc" and "gmp\_rational.cc" for GMP
which cdd+ can now use instead of GNU's G++ Rational arithmetic library.
Since cdd+ with GMP runs substantially faster
than cddr+ with g++Rational, any cdd+ user who needs exact arithmetic
computation is strongly recommended to use the GMP version.
One should be also aware that GMP-2.0.2 has known bugs and
all the patches available from GMP-Homepage
(\htmladdnormallink{http://www.matematik.su.se/~tege/gmp/}
{http://www.matematik.su.se/~tege/gmp/})
should be applied first.
Even with all these troubles, its speed compensates them easily.
How much faster? It all depends on your data. For kkd* polytopes
included in cdd+, cddr+\_gmp runs three to ten times faster than
cddr+\_g++. For less complicated polytopes, the speedup might be modest
but one can expect the gmp version runs always faster.
\section{Introduction} \label{INTRODUCTION}
The program cdd+ (cdd, respectively) is
a C++ (ANSI C) implementation of
the Double Description Method~\cite{mrtt-ddm-53}
for generating all vertices (i.e. extreme points)
and extreme rays of a general
convex polyhedron given by a system of linear inequalities:
\[
P = \{ x \in R^d: A x \le b \}
\]
where $A$ is an $m \times d$ real matrix and $b$ is a real
$m$ dimensional vector. See, \cite{fp-ddmr-96} for
an efficient implementation of the double description
method which is employed in cdd+.
One useful feature of cdd/cdd+ is its capability
of handling the dual (reverse) problem without any transformation
of data. The dual problem is known to be the
{\em (convex) hull problem\/} which
is to obtain a linear inequality representation
of a convex polyhedron given as the Minkowski sum of
the convex hull of a finite set of points and the nonnegative
hull of a finite set of points in $R^d$:
$P = conv(v_1,\ldots,v_n) + nonneg(r_1,\ldots,r_s)$, where
the {\em Minkowski sum of two subsets $S$ and $T$} of $R^d$ is defined
as $S + T = \{ s + t \; | s \in S \mbox{ and } t \in T \}$.
As we see in this manual, the computation can be done
in straightforward manner. There is one assumption for the input
for hull computation: the polyhedron must be full-dimensional.
Besides these basic functions, cdd/cdd+ can solve the general
linear programming (LP) problem to maximize (or minimize) a linear
function over polyhedron $P$. It is useful mainly for solving
dense LP's with large $m$ (say, up to few hundred thousands) and small $d$
(say, up to 100).
The program cdd+ is a C++ program, converted from the ANSI C
program cdd in 1995. Both programs have been updated for a few times since then.
One major advantage of this C++-version over the C version 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.3 or higher) gcc compiler
and g++-lib. One should be also warned that the computation
can be considerably (10 - 100 times or even more) slower if the rational
arithmetic is used. My idea is to keep the ANSI C code cdd as simple as
as possible, while the C++ code cdd+ will be used to be an experimental
platform to test new ideas.
The program cdd/cdd+ reads input and writes output in
{\em Polyhedra format\/} which was defined by David Avis and
the author in 1993, and has been updated in 1997.
The program called lrs \cite{a-uglrs-97} developed by David Avis is
a C-implementation of the reverse search algorithm~\cite{af-pachv-92}
for the same enumeration purpose, and it conforms to Polyhedra format as well.
Hopefully, this compatibility of the two programs
enables users to use both programs for the same input files
and to choose whichever is useful for their purposes.
From our experiences with relatively large problems,
the two methods are both useful and perhaps complementary
to each other. In general, the program cdd+ tends to be
efficient for highly degenerate inputs and the program rs
tends to be efficient for nondegenerate or slightly
degenerate problems.
Among the hardest problems that could be
solved (in floating-point arithmetic) by cdd+ is a
21-dimensional hull problem given by 64
vertices. This polytope, known as the {\em complete
cut polytope on 7 points\/}, has exactly 116,764 facets
and some of facets contain many vertices.
It took 205 hours (eight and half days!) for cdd
to compute the facets exactly on a SUN SparkServer 1000.
The input file (ccp7.ine) of this polytope is
included in the distribution. A considerably easier
problem is ccc7.ine which is a variation of the problem
(see e.g. \cite{g-afccn-90}).
The size of an input file hardly indicates the degree of
hardness of its vertex/ray enumeration. While this program
can handle a highly degenerate problem (prodmT5.ine) with
711 inequalities in 19 dimension quite easily with
the computation time 1-2 minutes on a fast workstation,
a 8-dimensional problem (mit729-9.ine) with 729 inequalities
can be extremely hard. It takes two days to compute all
(only 4862) vertices by a SUN SparkServer 1000. The latter problem arises
from the ground state analysis of a ternary alloy model, see \cite{cgaf-gstfl-94}.
Both input files are included in the distribution.
Although the program can be used for nondegenerate inputs,
it might not be very efficient. For nondegenerate inputs,
other available programs, such as the reverse search code lrs or
qhull (developed by the Geometry Center),
might be more efficient. See Section~\ref{CODES}
for pointers to these codes.
The paper \cite{abs-hgach-97} contains many interesting results on polyhedral
computation and experimental results on cdd+, lrs, qhull and porta.
This program can be distributed freely under the GNU GENERAL PUBLIC LICENSE.
Please read the file COPYING carefully before using.
I will not take any responsibility of any problems you might have
with this program. But I will be glad to receive bug reports or suggestions
at the e-mail addresses above. Finally, if cdd+ turns out to be useful,
please kindly inform me of what purposes cdd has been used for.
I will be happy to include a list of applications in future
distribution if I receive enough replies.
The most powerful support for free software development
is user's appreciation and collaboration.
\section{Polyhedra H- and V-Formats (Version 1997)} \label{FORMAT}
\bigskip
Every convex polyhedron has two representations, one as
the intersection of finite halfspaces and the other
as Minkowski sum of the convex hull of finite points
and the nonnegative hull of finite directions. These are
called H-representation and V-representation, respectively.
Naturally there are two basic Polyhedra formats,
H-format for H-representation and V-format for
V-representation. These two formats are designed
to be almost indistinguishable, and in fact, one can
almost pretend one for the other. There is some asymmetry
arising from the asymmetry of two representations.
First we start with the halfspace representation.
Let $A$ be an $m \times d$ matrix, and let $b$ be a column $m$-vector.
The Polyhedra format ({\em H-format} ) of
the system $ A x \le b$ of $m$ inequalities in $d$ variables
$x =(x_1, x_2, \ldots, x_d)^T$ is
\begin{tabular}{ccl}
\\ \hline
\multicolumn{3}{l} {various comments}\\
\multicolumn{3}{l} {{\bf H-representation}}\\
\multicolumn{3}{l} {{\bf begin}}\\
$m$ & $d+1$ & numbertype\\
$b$ & $-A$ \\
\multicolumn{3}{l} {{\bf end}}\\
\multicolumn{3}{l} {various options} \\ \hline
\end{tabular}
\bigskip
\noindent
where numbertype can be one of integer, rational or real.
When rational type is selected, each component
of $b$ and $A$ can be specified by the usual integer expression
or by the rational expression ``$p / q$'' or ``$-p / q$'' where
$p$ and $q$ are arbitrary long positive integers (see the example
input file rational.ine). In the new 1997 format,
we introduced ``H-representation'' which must appear
before ``begin''.
There was one restriction in the old polyhedra format
(before 1997): the last $d$ rows must determine
a vertex of $P$. This is obsolete now.
Now we introduce Polyhedra {\em V-format}. Let $P$ be
represented by $n$ extreme points and $s$ rays as
$P = conv(v_1,\ldots,v_n) + nonneg(r_1,\ldots,r_s)$.
Then the Polyhedra V-format for $P$ is defined as
\begin{tabular}{ccl}
\\ \hline
\multicolumn{3}{l} {various comments}\\
\multicolumn{3}{l} {{\bf V-representation}}\\
\multicolumn{3}{l} {{\bf begin}}\\
$n+s$ & $d+1$ & numbertype\\
$1$ & $v_1$ & \\
$\vdots$ & $\vdots$ & \\
$1$ & $v_n$ & \\
$0$ & $r_1$ & \\
$\vdots$ & $\vdots$ & \\
$0$ & $r_s$ & \\
\multicolumn{3}{l} {{\bf end}}\\
\multicolumn{3}{l} {various options} \\ \hline
\end{tabular}
\bigskip
\noindent
Here we do not require that
vertices and rays are listed
separately; they can appear mixed in arbitrary
order. Before the year 1997,
the option ``hull'' was used instead of ``V-representation''
in V-format. The old option is obsolete but cdd+ still
understands this option for backward compatibility.
The reverse search code lrs has employed this new format
from version 3.2.
When the representation statement, either ``H-representation''
or ``V-representation'', is omitted, the former
``H-representation'' is assumed.
It is strongly suggested to use the following rule for naming
H-format files and V-format files:
\begin{description}
\item[(a)] use the filename extension ``.ine'' for H-files (where ine stands for inequalities), and
\item[(b)] use the filename extension ``.ext'' for V-files (where ext stands for extreme points/rays).
\end{description}
The program cdd+ does two transformations, one from an H-format
to a V-format, and the reverse. While an input file (in H-format or V-format)
can have redundant information, cdd+ outputs a minimal representation
(in V-format or H-format).
For example, let $P$ be the following unbounded 3-dimensional
H-polyhedron given by
\[
P = \{ x \in R^3:
1\le x_1 \le 2, \; 1 \le x_2 \le 2, \; 1 \le x_3, \; x_1 + x_2 \le 4 \},
\]
which is a 3-cube without one ``lid''. The last inequality is redundant
because it is implied by $x_1 \le 2$ and $x_2 \le 2$. This is added
to show how cdd+ works with redundant data.
For finding all
vertices and extreme rays, the input file for cdd+ is
\begin{verbatim}
* file name: ucube.ine
* 3 cube without one "lid"
H-representation
begin
6 4 integer
2 -1 0 0
2 0 -1 0
-1 1 0 0
-1 0 1 0
-1 0 0 1
4 -1 -1 0
end
incidence
adjacency
input_adjacency
input_incidence
\end{verbatim}
The meaning of options ``incidence'', ``adjacency''
``input\_adjacency'' and ``input\_incidence''
will be explained in Section~\ref{OPTIONS}.
After you run cddr+ (the rational arithmetic version of cdd+) or cddf+
with this input file, you will get
an output file ucube.ext which is the minimal V-representation
of the polyhedron:
\begin{verbatim}
* cdd+: Double Description Method in C++:Version 0.76 (March 17, 1999)
* Copyright (C) 1999, Komei Fukuda, fukuda@ifor.math.ethz.ch
* Compiled for Rational Exact Arithmetic with GMP
*Input File:ine/ucube.ine(6x4)
*HyperplaneOrder: LexMin
*Degeneracy preknowledge for computation: None (possible degeneracy)
*Vertex/Ray enumeration is chosen.
*Output adjacency file is requested.
*Input adjacency file is requested.
*Output incidence file is requested
*Input incidence file is requested.
*Computation completed at Iteration 6.
*Computation starts at Wed Mar 17 06:56:51 1999
* terminates at Wed Mar 17 06:56:51 1999
*Total processor time = 0 seconds
* = 0h 0m 0s
*FINAL RESULT:
*Number of Vertices =4, Rays =1
V-representation
begin
5 4 rational
1 2 1 1
1 1 1 1
1 1 2 1
1 2 2 1
0 0 0 1
end
hull
\end{verbatim}
The output shows that the polyhedron has four vertices
$(2,1,1)$, $(1,1,1)$, $(1,2,1)$, $(2,2,1)$ and
only one extreme ray $(0,0,1)$. The comments contain
information on the name of input file, and the options
chosen to run the program which will be explained in
the next section.
Now, if you run cdd+ with this output file ucube.ext,
cdd+ will perform the convex hull operation to recover
essentially the original inequalities. More precisely, if
we make a copy ucube2.ext of ucube.ext, and run
cddr+ (or cddf+) with this copy, it will create a new ucube2.ine file:
\begin{verbatim}
* cdd+: Double Description Method in C++:Version 0.76 (March 17, 1999)
* Copyright (C) 1999, Komei Fukuda, fukuda@ifor.math.ethz.ch
* Compiled for Rational Exact Arithmetic with GMP
*Input File:ucube2.ext(5x4)
.
.
.
*Number of Facets = 5
H-representation
begin
5 4 rational
-1 0 1 0
-1 1 0 0
2 0 -1 0
2 -1 0 0
-1 0 0 1
end
\end{verbatim}
It is easy to check that this H-representation is
essentially the same as the one we started with, except the
new one does not contain any redundant inequality and the orderings
are different.
Note that this back-and-forth transformation of a polyhedron works
only when a polyhedron admits a unique minimal V-representation
and a unique minimal H-representation.
For example, when a polyhedron is full dimensional and contains
at least one vertex, it satisfies these conditions.
\section{Options} \label{OPTIONS}
The following options are available for cdd. These options are
set if they appear in input file after the ``end'' command.
Independent options can be set simultaneously, but each option
must be written separately in one line, and two options
should not be written in one line. When two or more non-independent
options are specified, the last one overrides the others.
Also note that options are case-sensitive.
\begin{description}
\item[hull] option \\
This old option exists only for the sake of
backward compatibility. This is to enforce
the computation to be convex hull computation,
interpreting the current data as a V-representation.
Use V-representation instead.
\item[verify\_input] option\\
When this option is chosen, the program will
output the input problem as cdd+ interpreted.
The default output file is ``*.solved''.
This option helps user to verify what problem
is actually solved. The default for this option is off.
See the sample files verifyinput1.ine and verifyinput2.ine
\item[dynout\_off] option\\
When this option is chosen, the program will
not output vertices and rays to the CRT in real time.
The default is dynout\_on.
\item[stdout\_off] option\\
When this option is chosen, the program will not
output any progress report of computation (iteration number. etc).
The default is stdout\_on.
\item[logfile\_on] option\\
When this option is chosen, the program will output
to a specified file (*.ddl) some information on the computation history.
This can be useful when the user does not know which hyperplane order
(mincutoff, maxcutoff, mixcutoff, lexmin, lexmax, minindex, random)
is efficient for computation.
\item[incidence, input\_incidence, \#incidence] options\\
When the {\bf incidence} option is selected, the incidence relation for
each {\bf output} with respect to input will be generated. The default filename
is *.icd if {\bf output} is inequalities (i.e. *.ine), and *.ecd
\footnote {In earlier versions, *.icd was used for the new *.ecd file.}
if {\bf output} is extreme points and
rays (i.e. *.ext).
When the {\bf input\_incidence} option is selected, the incidence relation for
each {\bf input} with respect to output will be generated. The default filename
is *.icd if {\bf input} is inequalities (i.e. *.ine), and *.ecd
if {\bf input} is extreme points and
rays (i.e. *.ext). This option was added to cdd+ ver. 0.74 and
{\bf not available in cdd\/}.
Here, an extreme point is said to be
{\em incident with\/} an inequality if the inequality is satisfied by equality.
An extreme ray $r$ is said to be {\em incident with\/}
an inequality $a^T \; x \le b$ if $a^T \; r = 0$.
For example,
since the incidence option was set for the example input file ucube.ine in
the previous section, the program outputs the following ucube.ecd file:
\begin{verbatim}
*Incidences of output(=vertices/rays) and input (=hyperplanes)
* for each output, #incidence and the set of hyperplanes containing it
* or its complement with its cardinality with minus sign
*cdd input file : ucube.ine (6 x 4)
*cdd output file: ucube.ext
begin
5 6 7
3 : 1 4 5
3 : 3 4 5
3 : 2 3 5
-3 : 3 4 7
-1 : 5
end
\end{verbatim}
After ``begin'', there are three numbers $5 \quad 6 \quad 7$.
The first number $5$ is a number of output (vertices and rays).
The next number $6$ is $m$, the number of inequalities in the input file.
The last number $7$ is usually $m+1$, and $m$ if the input linear inequality
system is homogeneous (i.e., has zero RHS) or the hull option is chosen.
The number $m+1$ corresponds to the infinity constraint which is added
for vertex/ray enumeration when the input system is not homogeneous.
The incidence data starts right after these three numbers.
At each line, the cardinality of incident inequalities and
the list of their indices are given. There is an exception that, when
there are more incident inequalities than non-incident ones, then the program
outputs the list of non-incident inequalities with its
size with negative sign. This is to save space of output.
For example, the first output line $3 \; : \; 1 \; 4 \; 5$
corresponds to the
first vertex of ucube.ext file in previous section, that is,
the vertex $(2, 1, 1)$. The first number $3$ is simply the number
of incident inequalities and the rest is the indices of
those inequalities, and so the 1st, 4th and 5th inequalities are
satisfied by equality at this vertex. The last output
$-1 \; : \; 5$ corresponds to the ray $(0,0,1)$. Since all inequalities
except the last (5th) inequality are incident with this ray,
the output is the (shorter) complementary list with its cardinality (=1) with negative
sign. Note that the full list would be $6 \; : \; 1 \; 2 \; 3 \; 4 \; 6 \; 7$, where
$6$ is the infinity plane. One can ignore the infinity
plane for some purposes, but for analyzing the combinatorial
structure of polyhedra, it is
very important information.
Also, since the input\_incidence option was set for the example input file ucube.ine in
the previous section, the program outputs the following ucube.icd file:
\begin{verbatim}
*cdd input file : ucube.ine (6 x 4)
*cdd output file: ucube.ext
*Incidence of input (=inequalities/facets) w.r.t. output (=vertices/rays).
*row 7 is redundant;dominated by: 1 2 3 4 6
*row 6 is redundant;dominated by: 1 2
begin
6 5 5
-2 : 2 3
-2 : 1 2
-2 : 1 4
-2 : 3 4
-1 : 5
2 : 4 5
1 : 5
end
\end{verbatim}
After ``begin'', there are three numbers $6 \quad 5 \quad 5$.
The first number $6$ is a number of input (inequalities).
The next number $5$ is $m$, the number of vertices and rays in the output file.
The last number $5$ is always $m$ for all *.icd files. The remaining
lines can be interpreted similarly with ucube.ecd file. The input\_incidence
option is {\bf not available in cdd\/}.
The {\bf \#incidence} option can be used when you do not wish
to output the incidence file but to output only the cardinality of incidence
for each output, at the end of each output line.
The incidence files (adjacency file, input\_adjacency as well)
can be created independently
after *.ext file is created, see ``postanalysis'' option.
\item[nondegenerate] option\\
When this option is set, the program assumes that the input system
is not degenerate, i.e., there is no point in the space $R^d$ satisfying
more than $d$ inequalities of input with equality.
It will run faster with this option, but of course,
if this option is set for degenerate inputs, it is
quite possible that the output is incorrect.
The default is this option being off.
\item[adjacency] option\\
This option can be used when you want to output the adjacency of output.
When the output is the list of vertices and rays, the program will
output the adjacency list. For the example input ``ucube.ine'',
the following extra file ``ucube.ead'' \footnote{In earlier versions,
this was ``ucube.adj''} will be created:
\begin{verbatim}
*Adjacency List of output (=vertices/rays)
*cdd input file : ucube.ine (6 x 4)
*cdd output file: ucube.ext
begin
5
1 3 : 2 4 5
2 3 : 1 3 5
3 3 : 2 4 5
4 3 : 1 3 5
5 4 : 1 2 3 4
end
\end{verbatim}
The first number $5$ is simply the number of outputs of cdd, the
number of vertices and rays in this case.
The second line $ 1 \quad 3 \quad : 2 \quad 4 \quad 5$ says
that the first output of
ucube.ext file has degree (valency) $3$, and its three neighbors are
2nd, 4th and 5th output.
When the computation is to obtain the hull (inequality system),
the adjacency is of course that of inequalities (i.e. facets).
The adjacency file (incidence file, input\_adjacency file)
can be created independently
after *.ext file is created, see ``postanalysis'' option.
\item[input\_adjacency] option\\
This is for cdd+ and {\bf not available in cdd\/}.
This option is for outputing the adjacency of input inequalities.
Here, two inequalities are defined to be {\em adjacent\/} if
they are nonredundant and there is no third input inequality
which is satisfied with equality at all points of the polyhedron
that satisfy the two inequalities with equality.
In more intuitive language, two inequalities are adjacent
if each determine a facet of the polyhedron and the intersection
of the two facets is not contained in any other facet.
The default file name for this output is *.iad. This file
lists the redundancy information of input also. For the example
``ucube.ine'' above, the following ``ucube.iad'' will
be generated:
\begin{verbatim}
*Adjacency List of input (=inequalities/facets)
*cdd input file : ucube.ine (6 x 4)
*cdd output file: ucube.ext
*row 7 is redundant;dominated by: 1 2 3 4 6
*row 6 is redundant;dominated by: 1 2
begin
7
1 3 : 2 4 5
2 3 : 1 3 5
3 3 : 2 4 5
4 3 : 1 3 5
5 4 : 1 2 3 4
6 0 :
7 0 :
end
\end{verbatim}
Observe that the 6th inequality and the
artificially added 7th inequality (infinity)
are found redundant. The 7th inequality is redundant
because the first four facets intersects at
a single infinity point (corresponding to a unique extreme ray)
and hence the polyhedron has no infinity facet,
although the polyhedron is not bounded.
The input\_adjacency file can be created independently
after *.ext file is created, see ``postanalysis'' option.
While cdd+ uses both *.ine and *.ext files to compute the adjacency
of input, it can be computed very efficiently by linear programming technique,
using only the input data. This will be explained in
the Polyhedral computation FAQ \cite{f-pcfaq-97}.
\item[postanalysis] option\\
It is often more desirable to compute the adjacency,
input\_adjacency, incidence and input\_incidence relations
independently from the main (and often heavy) computation of enumerating all vertices
and extreme rays. The ``postanalysis'' option can be used together
with ``adjacency'' and/or ``incidence'' options for this purpose
to create *.adj and/or *.icd files from both *.ine and *.ext files.
If *.ine file contains this option, cdd+ will open the
corresponding *.ext file and output requested *.adj, *.iad and/or *.icd files.
An error occurs when *.ext file does not exist in the current
directory.
\item[lexmin, lexmax, minindex,mincutoff, maxcutoff, mixcutoff, random] options\\
The double description is an incremental algorithm which
computes the vertices/rays of a polyhedron given by some $k$ of
original inequalities from the precomputed vertices/rays of a
polyhedron given by $k-1$ inequalities. It is observed that
the efficiency of the algorithm depends strongly on how
one selects the ordering of inequalities, although a little
can be said theoretically.
These options are to select the ordering of inequalities to be
added at each iteration, and it is recommended to do small
experiment to select good ordering for a specific type of problems.
Unfortunately, a good ordering depends on the problem and there does not seem
to be THE BEST ordering for every computation. From our experiences,
lexmin, lexmax, mincutoff, maxcuoff work quite well in general.
The default is lexmin ordering which simply order inequalities
with respect to lexico-graphic ordering of rows of $(b, -A)$. The lexmax
is reverse of lexmin. The mincutoff (maxcutoff) option selects an inequality which
cuts off the minimum (maximum) number of vertices/rays of the $(k-1)$st polyhedron.
The mixcutoff option is the mixture of mincutoff and maxcutoff which selects
an inequality which cuts off the $(k-1)$st polytope as unbalanced as possible.
The maxcutoff option might be efficient if the input contains
many redundant inequalities (many interior points for hull computation).
The minindex option selects the hyperplanes from the top of
the input.
The random option selects the inequalities in a random order. This option
must be followed by a random seed which is positive integer (less than
65536). For example, {\bf random 123} specifies the random option with
the random seed 123.
\item[initbasis\_at\_bottom] option\\
When this option is set, the program tries to select
the initial set of rows for the double description
method from the bottom of the input. This means that
if the last (d+1) rows are independent,
they will be chosen to initiate the algorithm.
This option is {\em not\/} default. The default
follows the same ordering as the ordering
of inequalities chosen. This means that if {\bf lexmin\/}
is the ordering of inequalities, then the initial
independent rows
will be chosen sequentially with lexico-min ordering.
There are exceptions when this rule
is not applicable, i.e. when one of mincutoff or maxcutoff
options is chosen. In such cases, {\bf lexmin\/}
ordering will be chosen.
\item[maximize, minimize] options\\
When maximize option is set with an objective vector
$c_0\: c_1 \: c_2 \ldots c_d$, the program
simply solves the linear program: $\max c_0 + c_1 x_1 + c_2 x_2 +\cdots + c_d x_d$
over the input polyhedron $P$. The grammar is simply
\begin{tabular}{ccl}
\\ \hline
\multicolumn{3}{l} {various comments}\\
\multicolumn{3}{l} {\bf H-representation}\\
\multicolumn{3}{l} {\bf begin}\\
$m$ & $d+1$ & numbertype\\
$b$ & $-A$ \\
\multicolumn{3}{l} {\bf end}\\
\multicolumn{3}{l} {maximize} \\
\multicolumn{3}{l} { $c_0 \quad c_1 \quad c_2 \quad \cdots \quad c_d$ } \\ \hline
\\
\end{tabular}
The minimize option works exactly same way for minimization of
a linear objective function.
See the sample input file ``lptest.ine''. The program cdd
will output both primal and dual optimal solutions if the LP
is solvable. If the LP is infeasible (dual infeasible), then
it will output an evidence.
For the moment, one can use either the dual simplex
method (option ``dual-simplex'', default)
or the criss-cross method by Terlaky-Wang.
The latter method can be specified
by option ``criss-cross'' and is very sensible to the ordering
of inequalities. The ordering options such as maxindex, lexmin and
random will affect the behavior of this solver. Try to use
a different ordering, if the computation takes too much time.
Also, in order to see the intermediate LP sign tableau
one can use ``show\_tableau'' option. Also use ``manual\_pivot''
option to select pivots manually. Of course, these options are
intended for very small problems.
The minimize and maximize options should be used only in H-representation
(*.ine) files, and the output filename is ``*.lps''.
\item[find\_interior] option\\
This is for cdd+ and {\bf not available in cdd\/}.
When this option is set, the program solves the linear program:
$\max x_{d+1}$
subject to $ A x + e x_{d+1} \le b$, where $e$ is the
column vector of all $1$'s. If the optimum value is zero,
the polyhedron has no interior point. If the optimum value is
negative then the polyhedron is empty. If the LP is dual inconsistent,
then the polyhedron admits unbounded inscribed balls. To find any
interior point in this last case, one must add some inequality(ies)
to bound the polyhedron.
This option should be used only in H-representation
(*.ine) files, and the output filename is ``*.lps''.
\item[facet\_listing, vertex\_listing] options\\
These are for cdd+ and {\bf not available in cdd\/}.
When the option ``facet\_listing'' is set, the program checks for each i-th row of the input
whether the associated inequality $A_i x \le b_i$ determines a facet
of the polyhedron. This option should be used only in H-representation
(*.ine) files, and the output filename is ``*.fis''.
When the option ``vertex\_listing'' is set, the program
checks for each i-th row of the input
whether the associated point $v_i$ determines a vertex
of the polyhedron. This option should be used only in V-representation
(*.ext) files, and the output filename is ``*.vis''.
After *.vis or *.fis file (say test.vis) is obtained,
one can get the minimal nonredundant
system by using the included gawk script get\_essential:
\begin{verbatim}
% get_essential < test.vis >test\_ess.ine
\end{verbatim}
You must have a gnu gawk command accessible at
the current unix directory. One must edit the new file
test\_ess.ine slightly according to the instruction
written in the file.
\item[facet\_listing\_external, vertex\_listing\_external] options\\
These options can be used to apply facet\_listing and vertex\_listing
with a (possibly large) external file. When the option facet\_listing\_external
is set with *.ine file, cdd+ will open an external file *.ine.external (in H-format)
and verify for each inequality of the external file whether it changes the
original polyhedron (represented by *.ine) if it is added. The option
vertex\_listing\_external can be set in *.ext file and works similarly.
Since cdd+ reads each line of the external file one by one, the file
can be very large, say of few hundred thousands lines.
\item[tope\_listing] option\\
This is for cdd+ and {\bf not available in cdd\/}.
When this option is set, the program generates all full-dimensional
regions (which are sometimes called topes) of the arrangement
of hyperplanes $\{ h_i : i = 1,2, \ldots, m \}$, where
$ h_i = \{ x : A_i x \le b_i \}$. Each tope will be
represented by its location vector, i.e.
a sign vector in $\{+, -\} ^m$ whose $i$-component
indicates the (positive or negative) side of the hyperplane $h_i$
the tope is located. This procedure assumes that the input
polyhedron is full-dimensional and thus the vector of all $+$'s
determines a tope. This option should be used only in H-representation
(*.ine) files, and the output filename is ``*.tis''.
\item[partial\_enumeration, equality, linearity, strict\_inequality] options\\
With partial\_enumeration option
(or equivalently equality or linearity options),
one can enumerate only those
vertices and rays that are lying on the set of hyperplanes
associated with specified inequality numbers. If you want
to compute all vertices/rays lying on hyperplanes
associated with $k$ inequalities $i_1, i_2, \ldots, i_k$
($1 \le i_j \le m$), then
the option should be specified as
\begin{tabular}{ccl}
\\ \hline
\multicolumn{3}{l} {various comments}\\
\multicolumn{3}{l} {\bf H-representation}\\
\multicolumn{3}{l} {\bf begin}\\
$m$ & $d+1$ & numbertype\\
$b$ & $-A$ \\
\multicolumn{3}{l} {\bf end}\\
\multicolumn{3}{l} {partial\_enumeration} \\
\multicolumn{3}{l} { $k \quad i_1 \quad i_2 \quad \cdots \quad i_k$ } \\ \hline
\\
\end{tabular}
The {\bf strict\_inequality\/} option follows the same
grammar as partial\_enumeration or equality.
With this, cdd outputs only those vertices and rays not satisfying
any of the specified inequalities with equality. See the sample files,
partialtest1.ine and partialtest2.ine.
These options make no effect on LP maximization or minimization.
\item[preprojection] option\\
This option is for a preprocessing
of orthogonal projection of the polyhedron to the subspace of
$R^d$ spanned by a subset of variables.
That is, if the inequality inequality system is
of two-block form $A_1 x_1 + A_2 x_2 \le b$,
and the variable indices for $x_1$, say $1, 4, 6, 7$,
are listed in the input file as
\begin{tabular}{ccl}
\\ \hline
\multicolumn{3}{l} {\bf H-representation}\\
\multicolumn{3}{l} {\bf begin}\\
$m$ & $d+1$ & numbertype\\
$b$ & $-A$ &\\
\multicolumn{3}{l} {\bf end}\\
\multicolumn{3}{l} {preprojection} \\
\multicolumn{3}{l} { $4 \quad 1 \quad 4 \quad 6 \quad7$ } \\ \hline
\\
\end{tabular}
Then, cdd+ will output the inequality system,
$A_1 x_1 \le b$, together with the list $R$ of extreme
rays of the homogeneous cone $\{z: z \ge 0 \mbox{ and } z^T A_2 = 0 \}$.
Consequently, the inequality system
$\{ \quad r^T A_1 x_1 \le r^T b : \quad r \in R \}$
represents the projection of the original polyhedron onto
$x_1$-space with possible redundancy. The default file names
for the inequality system output and the extremal ray output are
*sub.ine and *.ext, respectively if the input file is named *.ine.
There is a supplementary C program, called domcheck,
written by F. Margot, EPFL, which generates quickly a minimal
(i.e. nonredundant) system from these two outputs.
This program can be obtained from the standard ftp site for cdd.
\item[zero\_tolerance] option\\
This option is for cdd+ and {\bf not available in cdd\/}.
This affects only the floating-point computation with cddf+.
This is to change the zero tolerance for floating point computation
to a user-specified value.
The default value is set in cddtype.h file as $10^{-6}$. This should not
be changed if you are not familiar with pitfalls of
floating-point computation. A tolerance value should follow the option
with blank(s) or a line break. If a tolerance is too small (e.g.
$10^{-20}$), or if it is too big (e.g. $0.1$), the computation
will most likely fail.
\item[round\_output\_off, output\_digits] options\\
These options are for cdd+ and {\bf not available in cdd\/}.
This affects only the floating-point computation with cddf+.
This is to modify the default output format of numbers. The default is
to output a number with 8 digits in scientific notation, except when
the nearest integer is within $10^{-6}$, it outputs the integer.
The first option is to cancel the latter rounding. This is recommended
when zero\_tolerance option above is used to change the tolerance.
The second option followed by a positive integer will set the number of
digits for each number to the integer.
\end{description}
\section{How to Use} \label{HOWTO}
The program hardly has any user interface. Once you have compiled
executable files, {\em cdd\/}, {\em cddf+\/} and {\em cddr+\/}
(see Section~\ref{sources_cdd} for cdd, Section~\ref{sources_cdd+} for cdd+),
and once you create an input file,
say, {\em test.ine\/}, you have basically two ways to run the program.
The simplest way is just to run cdd/cdd+ with
\begin{verbatim}
% cdd test.ine
\end{verbatim}
or
\begin{verbatim}
% cddf+ test.ine
\end{verbatim}
or, if you want to compute with rational (exact arithmetic)
\begin{verbatim}
% cddr+ test.ine
\end{verbatim}
Then the program will open necessary output files with
default file names as shown in Table~\ref{FIG:files}
and output the requested results.
\begin{table}[ht]
\begin{center}
\begin{tabular}{|l||l|l|} \hline
& \multicolumn{2}{c|} {Input File Format }\\
options & \multicolumn{1}{c|} {H-format (*.ine)} & \multicolumn{1}{c|} {V-format (*.ext)} \\ \hline
conversion & *.ext & *.ine \\
incidence & *.ecd & *.icd \\
input\_incidence & *.iad & *.ead \\
adjacency & *.ead & *.iad \\
input\_adjacency & *.iad & *.ead \\
maximize/minimize & *.lps & non applicable \\
facet\_listing & *.fis & non applicable \\
vertex\_listing & non applicable & *.vis \\
tope\_listing & *.tis & non applicable \\
verify\_input & *.solved & *.solved \\
preprojection & *sub.ine & non applicable \\
& and *.ext & \\ \hline
\end{tabular}
\end{center}
\caption{Default extensions for output files}
\label{FIG:files}
\end{table}
\bigskip \noindent
If you wish to specify the output file names
different from default, simply run the program by
\begin{verbatim}
% cdd (cddf+, cddr+)
\end{verbatim}
and input desired file names at each of file name requests.
Even after you run cdd this way, one can
change to the automatic mode by inputing the input file
name with additional semicolon, e.g. ``test.ine;''.
To test cdd/cdd+, it is suggested to run cdd+ with sample input files
which are stored in subdirectories {\bf ine} and {\bf ext}.
\section{Source Files and Compilation for cdd} \label{sources_cdd}
\begin{itemize}
\item[(1)] [Files and Compilation] The source files for distribution are
\begin{tabular}{ll}
cdd.c & C main source file\\
cddarith.c & C sub source file\\
cddio.c & C sub source 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 of this manual itself\\
makefile & makefile for cdd+ compilation\\
HISTORY.cdd & brief description of changes made at each updates\\
README.cdd+ & cdd+ readme file\\
ine & A subdirectory containing sample inequality files\\
ext & A subdirectory containing sample points files for hull computation\\
COPYING & GNU GENERAL PUBLIC LICENSE
\end{tabular}
\noindent
To compile the code in a standard unix environment (with GNU gcc compiler), type
\begin{verbatim}
make all
\end{verbatim}
to obtain an optimized executable file cdd and dplex\_test. If this does not work,
modify the file, Makefile. The GNU compiler gcc can be replaced by cc,
if aother ANSI C compiler cc is available.
Since the program includes some standard ANSI library
headers such as stdlib.h and time.h at compilation,
the compiler must know the locations of the standard ANSI libraries.
Also, the files cdd.c, cdd.h, cdddef.h, cddarith.c, cddio.c, dplex.c, dplexdef.h,
dplex.h, setoper.c and setoper.h are supposed to be
in the current directory.
\item[(2)] [Recompilation] The first two constants in the program dplexdef.h are to be
changed by the user if necessary, and the program must be recompiled
each time after any change is made. These constants are simply
to specify the largest size of acceptable input data $(b, -A)$:
\begin{verbatim}
#define dp_MMAX 5002 /* USER'S CHOICE: max row size of A plus two */
#define dp_NMAX 101 /* USER'S CHOICE: max column size of A plus one */
\end{verbatim}
If this input data has $m$ rows and $d+1$ columns, then in the program,
dp\_MMAX should be at least $m+1$ and dp\_NMAX should be at least
$d+1$. Although it has no sense to set the sizes
dp\_MMAX and dp\_NMAX much larger
than necessary, the program only creates spaces
for dp\_MMAX+dp\_NMAX pointers
and uses only necessary storage space for each input, and
thus large dp\_MMAX and dp\_NMAX won't be too harmful.
\item[(3)] [TURBO/THINK C Users] The program cdd.c is written in
ANSI C, and thus it should run on
personal computers without any changes if one uses a compliler supporting
ANSI standard. I have been using THINK C without
any problems if ANSI library is added to the project together with