-
Notifications
You must be signed in to change notification settings - Fork 2
/
cddHISTORY
309 lines (257 loc) · 14 KB
/
cddHISTORY
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
cdd & cdd+ HISTORY file (as of December 10, 1997)
*** cdd version (date) / changes ***
Version C0.21 (November 10, 1993) /
- The first version of cdd created by translating pdd.p (0.21) with
Dave Gillespie's p2c translator and by modifying the c-code. The set operation
libraries setoper.c, setoper.h (Nov.14, 1993) were created to make the code run
without any p2c libraries.
Version C0.22 (November 21, 1993) /
- File open procedures have been updated.
Version C0.23 (November 22, 1993) /
- First release of cdd.
Version C0.23a, b (November 23, 1993) /
- Few small bugs of C0.23 have been fixed.
- Up to this version, the program can deal with column size at most 32.
Version C0.24 (November 27, 1993) /
- Modified to be able to deal with column size (nn) larger than 32.
- Bugs of LexMin, LexMax ordering options are fixed.
Version C0.25 (November 28, 1993)
- The bug for mishandling the empty polyhedra input is fixed.
Accordingly, the new variable CompStatus (Completion Status)
has been added.
- The procedure AddNewHyperplane and EvaluateARay have been completely
changed. EvaluateARay computes A(hnew) * Ray for each Rays, and sort
the linked list of rays so that the hnew-infeasible rays will be
put consecutively from FirstRay.
Version C0.26 (November 29, 1993) /
- FindBasis has been modified to be faster when the number of inequalities is large.
- addition of #incidence option for outputting the cardinality of active
hyperplanes instead of the set of all active hyperplanes at each vertex.
- InitBasisAtBottom option has been added to select the last set of rows
as the initial basis (determining a simplex cone/polytope).
This option is {\em not\/} default. See User's manual.
Version C0.26b(December 8, 1993) /
- FindBasis and ComputeRank have been replaced with new programs which do not copy
Amatrix (for save storage and time). Accordingly, the procedure CopyAmarix has been
removed.
Version C0.27(December 8, 1993) /
- It uses a new versions of setoper.h and setoper.c (Dec 8, 1993 version) which have
set complemen procedure set_compl.
Version C0.31(December 20, 1993) /
- The main program cdd.c has been divided into two parts, cdd.c and cddarith.c, the latter
contains all the procedures dealing with floating point numbers and operations.
- LP solver CrissCrossSolve has been added. Now the option "maximize" can be used to
optimize any linear function over the polyhedron.
- The setoper library has been updated to accomodate set_card(set) function.
Version C0.32(Jan. 11, 1994) /
- "preprojection" option has been added. This option can be considered as a preprocessing
of orthogonal projection of the polyhedon to a subset of variables. That is, if the inequality
inequality system is of form A1 x1 + A2 x2 <= b, and the variable indices for x2, say 1, 4, 6, 7,
are listed in the input file as
-------------
begin
m n Type
b -A1 -A2
end
preprojection
4 1 4 6 7
-------------
Then, cdd will output the inequality system, A1 x1 <= b, together with the list R of extremal
rays of the homogeneous cone {z: z >=0 and z A2 = 0 }. Consequently, the inequality system
{r A1 x1 <= r b for each r in R} represents the projection of the original polyhedron onto
x1-space with possible redundancy. The supplementary C program (written by F. Margot)
will be used to obtain a minimal system from these two outputs.
Version C0.33(Jan. 16, 1994) /
- partial_enumeration option has been added. By this option, one can enumerate all vertices
and rays which are lying on a selected set of inequalities. The input
-------------
begin
m n Type
b -A1 -A2
end
partial_enumeration
4 1 4 6 7
-------------
restricts the enumeration for those lying on the 1st, 4th, 6th & 7th hyperplanes.
Version C0.34(Jan. 22, 1994) /
- adjacency option has been added to output the adjacency list of output.
Version C0.35(Jan. 23, 1994) /
- RayRecord struct has been modified to store only a pointer for a Ray vector so that
the necessary space for the vector is allocated each time. This saves a space for
storing each RayRecord.
Version C0.36(Jan. 23, 1994) /
- RayRecord struct has been modified to store only a pointer for a ZeroSet so that
the necessary space for the set is allocated each time. This saves a space for
storing each RayRecord ZeroSet. For this modification, the setoper library
must have been changed so that set_initialize allocates the minimum space.
Note that this new version (Jan. 23, 1994) does not work with the older cdd
programs.
Version C0.37(Jan. 25, 1994) /
- Amatrix struct has been modified to store only the row pointers.
Version C0.38(Jan. 31, 1994) /
- Bmatrix struct has been modified to store only the row pointers. Thus the program
does not use any 2-dim arrays, and uses mainly dynamic allocation memory as much
as necessary irrespective of the declared maximum size MMAX times NMAX.
Thus, even in Macintosh computers large problems can be solved.
- CrissCrossSolve LP solver has been updated to output dual solutions as well.
Version C0.50 (Feb. 7, 1994) /
- Major upgrade to implement a new data structure to store adjacencies of rays.
The adjacency record lists, Edges(iteration), are used to store only necessary
adjacencies for each iteration. This version runs much faster unless
a dynamic ordering of rows (i.e. maxcutoff or mincutoff) is chosen.
The users are strongly discouraged to use these dynamic ordering options.
Version C0.51 (Feb. 12, 1994) /
- Some bugs of Version C0.50 has been fixed.
- The option "algebraic" for selecting the algebraic adjacency computation
is deleted. The reason is the combinatorial adjacency computation
is almost always faster.
- The option "minimize" is implemented to minimize a linear function over
the polytope. Previously, only "maximize" was supported.
- The option "find_interior" has been added to compute an interior point of
the input polyhedron.
Version C0.51a (Feb. 16, 1994) /
- A bug of Version C0.51 (mishandling of empty polyhedron) is fixed.
Version C0.51b (March 9, 1994) /
- A bug of Version C0.51a (mishandling of non full-dimensional
polyhedron) is fixed. The bug was reported by Alexander Bockmayr of
Max-Planck Institute.
Version C0.51c (March 15, 1994) /
- A bug of Version C0.51b (mishandling of homogeneous inputs, i.e. zero RHS)
is fixed. This bug was reported by Alexander Bockmayr of
Max-Planck Institute.
Version C0.52 (March 21, 1994) /
- A bug of Version C0.51c generating segmentation fault when the option
preprojection is used is fixed. This bug was reported by Alexander Bockmayr of
Max-Planck Institute.
- Some structural changes in the programs, cdd.c and cddarith.c, have been made
mainly for a future planning of adding an option to decompose a problem into
smaller subproblems.
Version C0.52a (March 28, 1994) /
- A bug of Version C0.52 generating unnecessary information when
maximize, minimize and find_interior are chosen is fixed.
Version C0.51d (March 28, 1994) /
- Because of the slowness of Version 0.52* due to unknown reasons, this version
has been produced for a temporary replacement. This version fixes the bug
mentioned in Version C0.52 release.
Version C0.52b (March 28, 1994) /
- The slowness problem of Version C0.52(a) is fixed.
Version C0.53 (July 29, 1994) /
- Some imcompatibility of cdd and domcheck has been fixed. Namely, one can
write any comments after each inequality data as long as it is written in
the same line as the last number (i.e., a_{id}, for each i) of each ith
inequality data. Anything written after the last number will be ignored.
Also, random ordering option is added for specifying the ordering of
rows (inequalities).
Version C0.54 (October 30, 1994) /
The partial_enumeration option is renamed as "equality" option.
A new option of "strict_inequality" is added to enumerate those
vertices/rays satisfying some specified inequalities with strict
inequality. Some bugs in reporting progress of iteration is fixed.
Version C0.55 (December 5, 1994) /
Set operation library setoper has been modified to use
the optimized set_card function by David Bremner. It is expected
that cdd runs much faster for problems with large row sizes.
The package organization has been changed. Now the package
consists of four C-programs, cdd.c, cddio.c, cddarith.c and setoper.c.
New options verify_input, equality and strict_inequality are added.
Also new options, lineshelling and row_decomposition are added but
these options are still not in very reliable form and not
recommended to use. Some newly found (minor) bugs are fixed.
Version C0.55a (December 18, 1994) /
The broken "preprojection" option in Version 0.55 is fixed.
Version C0.56 (August 7, 1995) /
Some compilation problem associated with incompatible set_type
variables in setoper.c is fixed. Various minor bugs are fixed.
The output format of incidence file is slightly modified. (See
the Reference Manual cddman.tex).
Version 0.60 (August 27, 1996) /
The following changes are equivalent to ones that had been made
for cdd+-074.
The default output file names have been changed to be consistent
with the transformation. To avoid confusion, *.ine file should
be used only for a system of linear inequalities, and *.ext file
only for a set of extreme points and rays. Accordingly,
the files *.ead (previously *.adj) and *.ecd (previously *.icd)
are reserved for the adjacency and incidence files for the extremal
vertices/rays.
Similarly, *.iad (previously *.iad) and *.icd (previously none)
are reserved for the adjacency and incidence files for the inequality
data.
The LP code is now independent of cdd, and rewritten as a C library.
This library is called dplex, and contains two algorithms,
the dual simplex and the criss-cross method.
Version 0.61 (December 1, 1997) /
It accepts "H-representation" and "V-representation" statements
which are added to a Polyhedra format (1997).
dp_FindInteriorPoint is added to dplex. Some small bugs are
fixed in dplex.
Version 0.61a (December 10, 1997) /
Practically the same as 0.61. Wrong dates written in the source are fixed.
*** cdd+ version (date) / changes ***
cdd+ Version 0.70 (April 3, 1995) /
The first C++ version of cdd which can run on both floating-point
and rational (exact) arithmetics. The basic functions are
identical to cdd-055. This version requires GNU gcc compilers
(2.6.0 or higher) and a compatible g++lib.
cdd+ Version 0.71 (April 15, 1995) /
Two new functions (through options) are added. The option
"facet_listing" checks whether each input inequality determines
a facet or not. The second option "tope_listing" generates
all full-dimensional regions (topes) of the associated
arrangement of hyperplanes by reverse search algorithm.
Also, the option "show_tableau" is added to illustrate
how the criss-cross method works in the tableau (dictornary)
form. Criss-cross LP solver is now sensitive to ordering
options, lexmin, minindex, radom, etc.
cdd+ Version 0.72 (April 16, 1995) /
The option "postanalysis" is added. This option is to be used
after *.ext file is obtained. When this option is set
with adjacency and/or incidence options, one can get
adjacency and incidence files from both *.ine and *.ext
files. Thus it is not necessary to generate *.adj and *.icd
files together with *.ext file.
cdd+ Version 0.72a (April 16, 1995) /
Cycling bug of Version 072 of LP maximize and minimize has been
fixed.
cdd+ Version 0.73 (Septembe 6, 1995) /
A new option "input_adjacency" has been added.
The output format of incidence file is slightly modified. (See
the Reference Manual cddman.tex). This incidence file format is compatible
with cdd-056 and we will try not to change the format any more.
cdd+ Version 0.74alpha (March 30, 1996) /
The default output file names have been changed to be consistent
with the transformation. To avoid confusion, *.ine file should
be used only for a system of linear inequalities, and *.ext file
only for a set of extreme points and rays. Accordingly,
the files *.ead (previously *.adj) and *.ecd (previously *.icd)
are reserved for the adjacency and incidence files for the extremal
vertices/rays.
Similarly, *.iad (previously *.iad) and *.icd (previously none)
are reserved for the adjacency and incidence files for the inequality
data.
Also, when a file with default file name exists in the current
directory, the default extension name will be doubled. For instance,
if test.ine is input and test.ext exists, then the extreme points
and rays will be written in the file test.ext.ext. The program
does not check "test.ext.ext" exists, and thus such a file
will be overwritten if exists.
cdd+ Version 0.74beta (June 4, 1996) /
The option "vertex_listing" is added.
The dual simplex method uses the standard Phase I instead of
the criss-cross method. Consequently the LP code is faster.
cdd+ Version 0.74beta2 (June 5, 1996) /
Also "vertex_listing_external" and "facet_listing_external"
are added. These options do "vertex_listing" and "facet_listing"
against the external file which can be huge. These options are
useful when one has a small candidate set of vertices (or inequalities)
and a large set of perhaps-redundant points (or inequalities).
The external file must be named as "test.ext.external" (test.ine.external)
if the candidate input file is test.ext (test.ine).
cdd+ Version 0.74 (June 17, 1996) /
Few minor bug fixes were made.
cdd+ Version 0.75 (November 30, 1997) /
This is a maintenance update of the previous version to employ the
new 1997 Polyhedra format (introducing H-representation and
V-representation statements). Three options for accuracy control
is added: "zero_tolerance", "round_output_off" and "output_digits".
--- end of file: cddHISTORY ---