third_party/cddlib/ChangeLog

libcdd, cdd & cdd+ HISTORY file   (as of April 30, 2015)

*** libcdd version (date) / changes ***

Version 094h (April 30, 2015) /
 - Thanks to Mathieu Dutour, one minor bug has been fixed.

Version 094g (March 23, 2012) /
 - 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.

Version 094f (February 7, 2008) /
 - 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.

Version 094e (January 27, 2008) /
 - 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.

Version 094d (February 12, 2007) /
 - 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.

Version 094c (April 23, 2006) /
 - 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.

Version 094b (August 25, 2005) /
 - 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.

Version 094a (August 24, 2005) /
 - A bug of dd_LPSolve is fixed.  This bug, reported by
   Dima Pasechnik, due to a mishandling of cycling of LP
   algorithms, is fixed.

Version 094 (August 4, 2005) /
 - 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.


Version 093d (February 27, 2005) /
 - 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.

Version 093c (December 26, 2003) /
 - 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.

Version 093b (November 10, 2003) /
 - 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.

Version 093a (Augst 11, 2003) /
 - 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.

Version 093 (July 18, 2003) /
 - 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.)   

Version 092b (October 19, 2002) /
 - 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.

Version 092a (December 19, 2001) /
 - 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.

Version 092 (December 12, 2001) /
 - 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.

Version 091d (March 9, 2001) /
 - Memory leak in dd_FreeLPData and dd_FreeLPSolution are
   fixed.

Version 091c (February 27, 2001) /
 - Bug to terminate before the completion of computation
   (to produce a segmentation fault) is fixed.  This
   bug was reported by Hugh Anderson.

Version 091b (February 26, 2001) /
 - 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.   

Version 091a (February 16, 2001) /
 - 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.

Version 091 (Sept. 25, 2000) /
 - 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.

Version 090e (July 12, 2000) /
 - 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.

Version 090d (June 25, 2000) /
 - 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.

Version 090c (June 12, 2000) /
 - 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.

Version 090b (June 2, 2000) /
 - 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.

Version 090a (May 30, 2000) /
 - a small bug fix in cddarith.c.  The bug is reported by Shawn Rusaw.

Version 090 (May 28, 2000) /
 - 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.  

Version 086 (Jan 22, 2000) /
 - 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.

Version 085 (October 4, 1999) /
 - 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.

Version 080 (March 24, 1999) /
 - 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.


*** cdd version (date) / changes ***

Version 0.61a (December, 1997) /
   Few minor corrections over 0.61.

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.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 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 C0.55a (December 18, 1994) /
   The broken "preprojection" option in Version 0.55 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.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.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.52b (March 28, 1994) /
 - The slowness problem of Version C0.52(a) 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.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.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.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.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.51a (Feb. 16, 1994) /
 - A bug of Version C0.51 (mishandling of empty polyhedron) is fixed.
 
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.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.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.37(Jan. 25, 1994) /
 - Amatrix struct has been modified to store only the row pointers.

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.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.34(Jan. 22, 1994) /
 - adjacency option has been added to output the adjacency list of output.
 
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.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.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.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.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.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.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.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.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.23 (November 22, 1993) /
 - First release of cdd.

Version C0.22 (November 21, 1993) /
 - File open procedures have been updated.

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.

*** cdd+ version (date) / changes ***

cdd+ Version 0.77beta (April 20, 2003) /
   This version is made so that it can be compiled with
   newer gcc. such as gcc 3.1.*.

cdd+ Version 0.76 (March 17, 1999) /
   This is functionally the same as Ver. 075.  This version can
   be compiled to run with GNU's GMP rational arithmetic library using
   Polymake's GMP-wrappers.  cddr+ with GMP runs much faster than
   the previous versions of cddr+ (with g++ Rational library). 

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

cdd+ Version 0.74 (June 17, 1996) /
   Few minor bug fixes were made.

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.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.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.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.72a (April 16, 1995) /
   Cycling bug of Version 072 of LP maximize and minimize has been 
   fixed.
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.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.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.


--- end of file: cddHISTORY ---