forked from cddlib/cddlib
-
Notifications
You must be signed in to change notification settings - Fork 0
/
ChangeLog
326 lines (278 loc) · 12.1 KB
/
ChangeLog
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
=================
cddlib Change Log
=================
.. current developments
v0.94l
====================
**Fixed:**
* `extern C` block in cdd.h header for C++ (thanks to @jengelh)
v0.94k
====================
- header files are now installed to PREFIX/include/cddlib to avoid clashes
with other libraries.
- configuration file for pkg-config added: assuming cddlib installed in
<prefix> known to pkg-config, "pkg-config --cflags cddlib" etc will
work. (Otherwise, one would need PKG_CONFIG_PATH=<prefix>/lib/pkgconfig).
v0.94jg
====================
- Thanks to Julian Rüth, modernized autotooling, mirrored
code on GitHub, introduced cddexec as a replacement of
cdd_both_reps that many distributions packaged, made
randomization portable. Thanks to Matthias C. M. Troffaes, fixed
representation type in dd_MatrixAppendTo.
v094ig
====================
- The missing definition of dd_set_d function in the case of
-DGMPRATIONAL flag is used. The only change is in cddmp.h.
The use of this function is explained in testcdd2.c program.
This function is useful when input is mostly float (real).
Even such a case, running on the rational exact arithmetic
might be helpful to debug the floating point computation.
v094hg
====================
- Thanks to Mathieu Dutour, one minor bug has been fixed.
v094gg
====================
- Thanks to both Anders Jensen and Mathieu Dutour
a few memory leaks in cddlib.c and cddlp.c have been
fixed. Also, some patches sent by Jerry James have
been applied. These were for making the library
shared and more compatible for C++ compilers.
v094fg
====================
- Thanks to Sven Verdoolaege's fixes,
the "configure" script now uses "gcc" as the default
compiler, rather than "g++" in earlier releases,
and the libraries can be linked properly with
both C and C++ programs.
v094eg
====================
- A bug of reporting a wrong (sign) certificate of
an infeasible LP is fixed. This bug reported by
Charles Geyer, occurs if the exact GMP version of
the dd_LPSolve is used with minimization. A bug of
reporting infeasibility of a feasible LP with
column non-full rank LP is fixed. This bug was reported
by Sven Verdoolaege.
v094dg
====================
- A bug of reporting a wrong unbounded direction vector of
a dual inconsistent LP is fixed. This bug occurs only
if the exact GMP version of the dd_LPSolve is used.
For example, this error may occur in scdd_gmp. This
error was reported by Lars Schewe.
v094cg
====================
- A bug for reading a rational number of length longer
than 255 characters have been fixed. This was reported
by Ruriko Yoshida. Now the longest
number is controlled by dd_wordlenmax defined in
cddtypes.h . The longest line is also controlled by
dd_linelenmax . These are currently fixed to
1024 and 4096. Larger numbers and lines can be
handled by modifying these numbers and recompilation.
v094bg
====================
- A bug for the representation conversion, reported by
Michal Kvasnica, was fixed. The earlier 094* versions
prematurely terminate the conversion when the number
of rows is equal to the number of columns in the input.
This means the earlier 094* do not compute correctly
for simplices, for example.
v094ag
====================
- A bug of dd_LPSolve is fixed. This bug, reported by
Dima Pasechnik, due to a mishandling of cycling of LP
algorithms, is fixed.
v094g
====================
- dd_MatrixCanonicalize has been added. This reduces
matrix M to a minimal representation by computing
all implicit linearity rows and all redundant rows.
It applies lexicographic sorting of rows to remove
duplicates before applying redundancy removal.
This function combines the two computations together
in more efficient manner than before.
See the new redcheck.c for its use. Several basic
operations for matrices have been added, such as
dd_MatrixRowsRemove and dd_MatrixRowsRemove2.
The representation conversion dd_DDMatrix2Poly now
handles the empty H-polyhedra properly, by calling
an LP-based emptiness checker before running the double
description algorithm.
New functions finding specific points in H-polyhedra
are added. dd_ExistsRestrictedFace is a general inequality
system solver with specified equations, inequalities and
strict inequalities. dd_FindRelativeInterior finds
a point in the relative interior of a polyhedron.
v093dg
====================
- The problem of outputting the running log has been corrected.
This problem and a solution was communicated by Charles Geyer.
Now, a new global dd_boolean variable dd_log (= dd_FALSE by default)
controls log output. An scdd/lcdd bug of terminating with segmentation
fault when an input polyhedron is numerically delicate has been
corrected. This bug was reported by Stefan Volkwein.
v093cg
====================
- A bug of Phase I of the dual simplex method in floating-point
arithmetics is fixed. The problem (bus error) occurred when input data
is not appropriate for floating-point arithmetics. The problem
occurrs even for the GMP executables as the exact LP solver first
tries to detect the terminal basis with float-point arithmetics.
v093bg
====================
- The nonterminating problem of the LP solver has been fixed.
This was due to a cycling of the criss-cross method in
floating-point arithmetics, that is extremely rare.
Also, the phase I of the dual simplex method has been
modified. The auxiliary LP is perhaps less likely to
be degenerate.
v093ag
====================
- The LP basis finding procedure dd_FindLPBasis2 has been
updated. The functions dd_Matrix2WeakAdjacency, dd_SRedundant and
dd_SRedundantRows are added. The manual has been updated.
v093g
====================
- dd_LPSolve with GMP now runs fisrt with floating point arithmetics
and checks with GMP the correctness of the result. New functions dd_Matrix2Adjacency,
dd_FourierElimination, dd_BlockElimination, dd_DDMatrix2Poly2 are added.
Some minor memory leak problems are fixed. (Thanks to the excellent
memory debugger valgrind on linux.)
v092bg
====================
- An illegal memory access for EqualityIndex reported by
Thao Dang is fixed. Another bug of lcdd_gmp which takes
"real" data and return a false result is fixed. It now warns
that input is not correct for the exact arithmetic lcdd_gmp.
This error was reported by Andras Salamon.
v092ag
====================
- Joerg Rambau kindly created an autoconf distribution of
cddlib-092. This version 092a is made from Rambau's
version with a slight modification. For the momoment,
the Mathematica cdd interface, cddmathlink (in src-mathlink),
still needs to be handled in the conventional manner by
editing Makefile.
v092g
====================
- the default value of dd_almostzero is now set to 1.0E-7
instead of 1.0E-6. New functions are added for checking
redundancy of H- and V- representations such as
dd_Redundant, dd_RedundantRows, dd_ImplicitLinearity,
dd_ImplicitLinearityRows, and dd_RayShooting.
Also some basic operations on dd_MatrixPtr have been added such as
dd_MatrixAppendTo, dd_MatrixRowRemove, dd_MatrixSubmatrix.
The names of enumeration type variables have been modified.
Now all names have prefix "dd_", e.g. Rational, Integer are
now dd_Rational and dd_Integer. This applies to TRUE and FALSE,
which are now dd_TRUE and dd_FALSE.
v091dg
====================
- Memory leak in dd_FreeLPData and dd_FreeLPSolution are
fixed.
v091cg
====================
- Bug to terminate before the completion of computation
(to produce a segmentation fault) is fixed. This
bug was reported by Hugh Anderson.
v091bg
====================
- Numerous memory leak bugs with GMP exact arithmetic,
reported by Marc Pfetsch, are fixed. Also, a minor
bug of cddlib to terminate with core dump, reported by
Hugh Anderson, is fixed. The messages printed to
the standard output "stdout" are now sent to "stderr".
This was suggested by Ingo Schurr.
v091ag
====================
- Memory leak problems when GMP is used are fixed for
dd_InitializeAmatrix, dd_CreateMatrix and
dd_Larger. These bugs, reported by Marc Pfetsch,
can be fatal if GMP is used and the functions are
called many times. It has no effect for floating-point
arithmetic computation.
v091g
====================
- Memory leak in FreeDDMemory (cddcore.c)
is fixed. This bug, which might cause a serious problem,
was reported by Shawn Rusaw. Also, a bug reported by
Istvan Csabai on dynamic row ordering is fixed. This
problem is most likely not affecting anyone, since the
dynamic row ordering option is not available via the
publicly released documentations. David Avis contributed
a sample cddlib code, lcdd.c, which runs like his convex
hull code, lrs. In particular, it is useful to generate
standard output stream for piping in unix.
v090eg
====================
- A bug of reading very large integer values incorrectly
is fixed. The previous versions were truncating very large
integer values to a number representable by long integer.
v090dg
====================
- Serious bugs of dd_CopyOutput, dd_CopyInequalities are fixed.
This bug is found by Istvan Csabai. Earlier versions 090*
output wrong H-representations whenever the RHS constants
are not nonnegative, even though the computation runs
correctly internally.
v090cg
====================
- set_intialize is modified so that it allocates a smallest space even when
a nonpositive length is requested.
The bug of not outputting the origin is fixed
when input is homogeneous inequality system and the cone contains
no extreme rays. Note that cddlib does not output this vertex
when the homogeneous cone has extreme rays, since cddlib outputs
a minimal representation.
- A new function dd_DDInputAppend is added.
- dd_DDMatrix2Poly replaces (and combines) the two old functions
dd_Matrix2Poly and dd_DoubleDescription.
- dd_LPSolutionLoad is renamed as dd_CopyLPSolution.
v090bg
====================
- Thanks to Shawn Rusaw's great help, I could detect and fix many
memory related problems (memory leak, out-of-bounds, etc).
Also, when input is not regular (nonfull or containing line),
cddlib did not generate adjacency/incidence properly and
this version should work more correctly.
v090ag
====================
- a small bug fix in cddarith.c. The bug is reported by Shawn Rusaw.
v090g
====================
- Major revision over the previous versions. It can be now compiled
with GMP rational (-DGMPRATIONAL) as well as the standard C double.
cdd and lp codes are merged and easily called together. Many functions
and data types are modified and renamed. It comes with a simple
cdd/cdd+-type standalne program scdd which does the standard
representation conversion (*.ine <-> *.ext) and outputs all four
types of auxiliary files (*.icd, *.iad, *.ecd, *ead). Although it
lacks some functions such as preprojection of cdd+, scdd is potentially
the most powerful cdd ever since it runs in the two arithmetics and
it can handle any input.
Because of the better readability and the overhead of employing
function calls to do GMP arithmetic, the speed is little slower than
cdd+-076 on both arithmetics C double and GMP rational.
v086g
====================
- A bug fixed in dd_LexSmaller that affercted the lexicographic
ordering of input data. This fix is essential for efficiency.
Also several memory leaks have been fixed. Many of these bugs
were found by Mr. Masanori Sato of Tokyo Institute of Technology.
Never released.
v085g
====================
- It can read rational data. Several minor bugs have been fixed.
The new makefile creates cdd and dplex library archives
libcdd.a and libdplex.a for unix systems.
v080g
====================
- The first C-library version of cdd. It is stilll very primitive
and has no documentation. See README.libcdd. Unlike the existing
versions of cdd/cdd+, cddlib can deal with essentially any input,
namely, non-full-dimensional convex hull problems and
vertex-free extreme point (i.e. generator) listing problems. Also
it comes with MathLink program cddmathlink that can be called from
Mathematica to perform cdd operations.