Added cddlib-094h from http://www.inf.ethz.ch/personal/fukudak/cdd_home/
Change-Id: I64519509269e434b1b9ea87c3fe0805e711c0ac9
diff --git a/third_party/cddlib/doc/cddlibman.tex b/third_party/cddlib/doc/cddlibman.tex
new file mode 100644
index 0000000..c55b8d6
--- /dev/null
+++ b/third_party/cddlib/doc/cddlibman.tex
@@ -0,0 +1,1180 @@
+% The name of this file: cddlibman.tex
+% written by by Komei Fukuda
+% created March 15, 1999
+% modified February 7, 2008
+%
+\documentclass[11pt]{article}
+\usepackage{html,amsmath,amssymb}
+\renewcommand{\baselinestretch}{1}
+\renewcommand{\arraystretch}{1}
+\setlength{\oddsidemargin}{0mm}
+\setlength{\textwidth}{165mm}
+\setlength{\topmargin}{-15mm}
+\setlength{\textheight}{232mm}
+%\setlength{\headsep}{0in}
+%\setlength{\headheight}{0pt}
+\pagestyle{plain}
+
+\newcommand {\0} {{\bf 0}}
+\newcommand{\R}{{\Bbb R}}
+
+\begin{document}
+\title{cddlib Reference Manual}
+\author{Komei Fukuda\\
+Institute for Operations Research\\
+and Institute of Theoretical Computer Science\\
+ETH Zentrum, CH-8092 Zurich, Switzerland\\
+}
+\date{ (cddlib ver. 0.94, manual ver. February 7, 2008)}
+
+\maketitle
+
+\tableofcontents
+
+\begin{abstract}
+This is a reference manual for cddlib-094.
+The manual describes the library functions and data types implemented
+in the cddlib C-library which is to perform fundamental polyhedral
+computations such as representation conversions and linear programming
+in both floating-point and GMP rational exact arithmetic.
+Please read the accompanying README file and test programs to
+complement the manual.
+
+The new functions added in this version include {\tt dd\_MatrixCanonicalize}
+to find a non-redundant proper H- or V-representation,
+{\tt dd\_FindRelativeInterior} to find a relative interior point
+of an H-polyhedron, and {\tt dd\_ExistsRestrictedFace} (Farkas-type
+alternative theorem verifier)
+to check the existence of a point satisfying a specified system
+of linear inequalities possibly including multiple strict inequalities.
+
+The new functions are particularly important for the development of
+related software packages MinkSum (by Ch. Weibel) and Gfan
+(by Anders Jensen),
+
+\end{abstract}
+
+\section{Introduction} \label{INTRODUCTION}
+
+The program cddlib is an efficient implementation \cite{fp-ddmr-96} 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=(x_1, x_2, \ldots, x_d)^T \in R^{d}: b - A x \ge 0 \}
+\]
+where $A$ is a given $m \times d$ real matrix and
+$b$ is a given real $m$-vector. In the mathematical
+language, the computation is the transformation
+of an {\em H-representation\/} of a convex polytope
+to an {\em V-representation}.
+
+cddlib is a C-library version of the previously released C-code cdd/cdd+.
+In order to make this library version, a large part of the cdd source
+(Version 0.61) has been rewritten.
+This library version is more flexible since it can be called from other programs in C/C++.
+Unlike cdd/cdd+, cddlib can handle any general input and is more general.
+Furtthermore, additional functions have been written to extend its functionality.
+
+One useful feature of cddlib/cdd/cdd+ is its capability
+of handling the dual (reverse) problem without any transformation
+of data. The dual transformation problem of a V-representation
+to a minimal H-representation and is often called the
+{\em (convex) hull problem\/}. More explicitly,
+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_{n+1},\ldots,r_{n+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. Unlike the earlier versions of
+cdd/cdd+ that assume certain regularity conditions for input,
+cddlib is designed to do a correct transformation for any general input.
+The user must be aware of the fact that in certain cases the
+transformation is not unique and there are polyhedra with
+infinitely many representations. For example, a line
+segment (1-dimensional polytope) in $R^3$ has infinitely
+many minimal H-representations, and a halfspace in the same space
+has infinitely many minimal V-representations. cddlib generates
+merely one minimal representation.
+
+cddlib comes with an LP code to 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). It implements a revised dual simplex method that
+updates $(d+1)\times (d+1)$ matrix for a pivot operation.
+
+The program cddlib has an I/O routines that read and write files in
+{\em Polyhedra format\/} which was defined by David Avis and
+the author in 1993, and has been updated in 1997 and 1999.
+The program called lrs and lrslib \cite{a-lrshome-01} 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 cddlib tends to be
+efficient for highly degenerate inputs and the program rs
+tends to be efficient for nondegenerate or slightly
+degenerate problems.
+
+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. If cddlib 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 1999)} \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 H-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 $\; b - A x \ge \0\;$ 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 (linearity $t\;$ $i_1\;$ $i_2\;$ $\ldots$ $\;i_t$)}}\\
+\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 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.
+
+In the new 1999 format, we added the possibility of specifying {\bf linearity\/}.
+This means that
+for H-representation, some of the input rows can be specified as {\bf equalities}:
+$b_{i_j} - A_{i_j} x = 0 \;$ for all $j=1,2, \ldots, t$.
+The linearity line may be omitted if there are no equalities.
+
+Option lines can be used to control computation of a specific program.
+In particular both cdd and lrs use the option lines to represent
+a linear objective function. See the attached LP files, samplelp*.ine.
+
+\bigskip
+Next we define Polyhedra {\em V-format}. Let $P$ be
+represented by $n$ gerating points and $s$ generating directions (rays) as
+$P = conv(v_1,\ldots,v_n) + nonneg(r_{n+1},\ldots,r_{n+s})$.
+Then the Polyhedra V-format for $P$ is
+
+\begin{tabular}{cll}
+\\ \hline
+\multicolumn{3}{l} {various comments}\\
+\multicolumn{3}{l} {{\bf V-representation}}\\
+\multicolumn{3}{l} {({\bf linearity $t\;$ $i_1\;$ $i_2\;$ $\ldots$ $\;i_t$ })}\\
+\multicolumn{3}{l} {{\bf begin}}\\
+ $n+s$ & $d+1$ & numbertype\\
+ $1$ & $v_1$ & \\
+ $\vdots$ & $\vdots$ & \\
+ $1$ & $v_n$ & \\
+ $0$ & $r_{n+1}$ & \\
+ $\vdots$ & $\vdots$ & \\
+ $0$ & $r_{n+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.
+
+Linearity for V-representation specifies a subset of generators
+whose coefficients are relaxed
+to be {\bf free}: for all $j=1,2, \ldots, t$, the $k=i_j$th generator ($v_{k}$ or $r_k$ whichever is the $i_j$th generator) is a free generator.
+This means for each such a ray $r_k$,
+the line generated by $r_k$ is in the polyhedron,
+and for each such a vertex $v_k$, its coefficient is no longer nonnegative
+but still the coefficients for all $v_i$'s must sum up to one.
+It is highly unlikely that one needs to
+use linearity for vertex generators, and it is defined mostly
+for formality.
+
+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}
+
+
+\section{Basic Object Types (Structures) in cddlib} \label{DATASTR}
+
+Here are the types (defined in cddtypes.h) that are
+important for the cddlib user. The most important one,
+{\tt dd\_MatrixType},
+is to store a Polyhedra data in a straightforward manner.
+Once the user sets up a (pointer to) {\tt dd\_MatrixType} data,
+he/she can load the data to an internal data type ({\tt dd\_PolyhedraType})
+by using functions described in the next section, and apply
+the double descrition method to get another representation.
+As an option {\tt dd\_MatrixType} can save a linear objective function
+to be used by a linear programming solver.
+
+The two dimensional array data in the structure {\tt dd\_MatrixType} is
+{\tt dd\_Amatrix} whose components are of type {\tt mytype\/}.
+The type mytype is set to be either the rational type {\tt mpq\_t} of
+the GNU MP Library or the C double array of size $1$.
+This abstract type allows us to write a single program that can
+be compiled with the two or more different arithmetics, see example
+programs such as simplecdd.c, testlp*.c and testcdd*.c
+in the {\tt src} and {\tt src-gmp} subdirectories of the source
+distribution.
+
+There is another data type that is used very often, {\tt dd\_SetFamilyType}.
+This is to store a family of subsets of a finite set. Such a family
+can represent the incidence relations between the set of extreme
+points and the set of facets of a polyhedron. Also, it can represent a
+graph structure by listing the set of vertices adjacent to each vertex (i.e.
+the adjacency list). To implement {\tt dd\_SetFamilyType},
+we use a separate set library called {\tt setoper}, that
+handles the basic set operations, This library is briefly introduced in
+Section~\ref{SetFunctions}.
+
+
+\begin{verbatim}
+
+#define dd_FALSE 0
+#define dd_TRUE 1
+
+typedef long dd_rowrange;
+typedef long dd_colrange;
+typedef long dd_bigrange;
+
+typedef set_type dd_rowset; /* set_type defined in setoper.h */
+typedef set_type dd_colset;
+typedef long *dd_rowindex;
+typedef int *dd_rowflag;
+typedef long *dd_colindex;
+typedef mytype **dd_Amatrix; /* mytype is either GMP mpq_t or 1-dim double array. */
+typedef mytype *dd_Arow;
+typedef set_type *dd_SetVector;
+
+typedef enum {
+ dd_Real, dd_Rational, dd_Integer, dd_Unknown
+} dd_NumberType;
+
+typedef enum {
+ dd_Inequality, dd_Generator, dd_Unspecified
+} dd_RepresentationType;
+
+typedef enum {
+ dd_MaxIndex, dd_MinIndex, dd_MinCutoff, dd_MaxCutoff, dd_MixCutoff,
+ dd_LexMin, dd_LexMax, dd_RandomRow
+} dd_RowOrderType;
+
+typedef enum {
+ dd_InProgress, dd_AllFound, dd_RegionEmpty
+} dd_CompStatusType;
+
+typedef enum {
+ dd_DimensionTooLarge, dd_ImproperInputFormat,
+ dd_NegativeMatrixSize, dd_EmptyVrepresentation,
+ dd_IFileNotFound, dd_OFileNotOpen, dd_NoLPObjective,
+ dd_NoRealNumberSupport, dd_NoError
+} dd_ErrorType;
+
+typedef enum {
+ dd_LPnone=0, dd_LPmax, dd_LPmin
+} dd_LPObjectiveType;
+
+typedef enum {
+ dd_LPSundecided, dd_Optimal, dd_Inconsistent, dd_DualInconsistent,
+ dd_StrucInconsistent, dd_StrucDualInconsistent,
+ dd_Unbounded, dd_DualUnbounded
+} dd_LPStatusType;
+
+typedef struct matrixdata *dd_MatrixPtr;
+typedef struct matrixdata {
+ dd_rowrange rowsize;
+ dd_rowset linset;
+ /* a subset of rows of linearity (ie, generators of
+ linearity space for V-representation, and equations
+ for H-representation. */
+ dd_colrange colsize;
+ dd_RepresentationType representation;
+ dd_NumberType numbtype;
+ dd_Amatrix matrix;
+ dd_LPObjectiveType objective;
+ dd_Arow rowvec;
+} dd_MatrixType;
+
+typedef struct setfamily *dd_SetFamilyPtr;
+typedef struct setfamily {
+ dd_bigrange famsize;
+ dd_bigrange setsize;
+ dd_SetVector set;
+} dd_SetFamilyType;
+
+typedef struct lpsolution *dd_LPSolutionPtr;
+typedef struct lpsolution {
+ dd_DataFileType filename;
+ dd_LPObjectiveType objective;
+ dd_LPSolverType solver;
+ dd_rowrange m;
+ dd_colrange d;
+ dd_NumberType numbtype;
+
+ dd_LPStatusType LPS; /* the current solution status */
+ mytype optvalue; /* optimal value */
+ dd_Arow sol; /* primal solution */
+ dd_Arow dsol; /* dual solution */
+ dd_colindex nbindex; /* current basis represented by nonbasic indices */
+ dd_rowrange re; /* row index as a certificate in the case of inconsistency */
+ dd_colrange se; /* col index as a certificate in the case of dual inconsistency */
+ long pivots[5];
+ /* pivots[0]=setup (to find a basis), pivots[1]=PhaseI or Criss-Cross,
+ pivots[2]=Phase II, pivots[3]=Anticycling, pivots[4]=GMP postopt */
+ long total_pivots;
+} dd_LPSolutionType;
+
+\end{verbatim}
+
+\section{Library Functions} \label{LIBRARY}
+
+Here we list some of the most important library functions/procedures.
+We use the following convention:
+{\tt poly} is of type {\tt dd\_PolyhedraPtr},
+{\tt matrix}, {\tt matrix1} and {\tt matrix2} are of type {\tt dd\_MatrixPtr},
+{\tt matrixP}, of type {\tt dd\_MatrixPtr*},
+{\tt err} is of type {\tt dd\_ErrorType*},
+{\tt ifile} and {\tt ofile} are of type {\tt char*},
+{\tt A} is of type {\tt dd\_Amatrix},
+{\tt point} and {\tt vector} are of type {\tt dd\_Arow},
+{\tt d} is of type {\tt dd\_colrange},
+{\tt m} and {\tt i} are of type {\tt dd\_rowrange},
+{\tt x} is of type {\tt mytype},
+{\tt a} is of type {\tt signed long integer},
+{\tt b} is of type {\tt double},
+{\tt set} is of type {\tt set\_type}.
+ Also,
+{\tt setfam} is of type {\tt dd\_SetFamilyPtr},
+{\tt lp} is of type {\tt dd\_LPPtr},
+{\tt lps} is of type {\tt dd\_LPSolutionPtr},
+{\tt solver} is of type {\tt dd\_LPSolverType},
+{\tt roworder} is of type {\tt dd\_RowOrderType}.
+
+
+\subsection{Library Initialization} \label{Initialization}
+
+\begin{description}
+
+\item[{\tt void dd\_set\_global\_constants(void)}]:\\
+This is to set the global constants such as {\tt dd\_zero},
+{\tt dd\_purezero} and
+{\tt dd\_one} for sign recognition and basic arithmetic
+operations. {Every program to use cddlib must call this function}
+before doing any computation. Just call this once.
+ See Section \ref{constants} for the definitions of
+constants.
+
+\item[{\tt void dd\_free\_global\_constants(void)}]:\\
+This is to free the global constants. This should be called
+when one does not use cddlib functions anymore.
+\end{description}
+
+\subsection{Core Functions} \label{CoreLibrary}
+
+There are two types of core functions in cddlib. The first type
+runs the double description (DD) algorithm and does a representation
+conversion of a specified polyhedron. The standard header
+for this type is {\tt dd\_DD*}. The second type solves
+one or more linear programs with no special headers.
+Both types of computations are nontrivial
+and the users (especially for the DD algorithm) must
+know that there is a serous limit in the sizes of problems
+that can be practically solved.
+Please check *.ext and *.ine files that come with cddlib to get
+ideas of tractable problems.
+
+In addition to previously defined objects, the symbol {\tt roworder} is
+of {\tt dd\_RowOrderType}. The symbol {\tt matrixP} is
+a pointer to {\bf dd\_MatrixType}.
+the arguments {\tt impl\_lin} and {\tt redset} are both a pointer
+to {\tt dd\_rowset} type, and {\tt newpos} is a pointer to
+{\tt dd\_rowindex} type.
+
+
+\begin{description}
+\item[{\tt dd\_PolyhedraPtr dd\_DDMatrix2Poly(matrix, err)}]:\\
+Store the representation given by {\tt matrix} in a polyhedra data, and
+generate the second representation of {\tt *poly}. It returns
+a pointer to the data. {\tt *err}
+returns {\tt dd\_NoError} if the computation terminates normally. Otherwise,
+it returns a value according to the error occured.
+
+\item[{\tt dd\_PolyhedraPtr dd\_DDMatrix2Poly2(matrix, roworder, err)}]:\\
+This is the same function as {\tt dd\_DDMatrix2Poly} except that the insertion
+order is specified by the user. The argument {\tt roworder} is of {\tt dd\_RowOrderType}
+and takes one of the values:
+ {\tt dd\_MaxIndex}, {\tt dd\_MinIndex}, {\tt dd\_MinCutoff}, {\tt dd\_MaxCutoff}, {\tt dd\_MixCutoff},
+ {\tt dd\_LexMin}, {\tt dd\_LexMax}, {\tt dd\_RandomRow}. In general, {\tt dd\_LexMin} is
+the best choice which is in fact chosen in {\tt dd\_DDMatrix2Poly}. If you know that
+the input is already sorted in the order you like, use {\tt dd\_MinIndex} or {\tt dd\_MaxIndex}.
+If the input contains many redundant rows (say more than $80\%$ redundant),
+you might want to try {\tt dd\_MaxCutoff} which might result in much faster termination,
+see \cite{abs-hgach-97,fp-ddmr-96}
+
+\item[{\tt boolean dd\_DDInputAppend(poly, matrix, err)}]:\\
+Modify the input representation in {\tt *poly}
+by appending the matrix of {\tt *matrix}, and compute
+the second representation. The number of columns in
+{\tt *matrix} must be equal to the input representation.
+
+\item[{\tt boolean dd\_LPSolve(lp, solver, err)}]:\\
+Solve {\tt lp} by the algorithm {\tt solver} and save
+the solututions in {\tt *lp}. Unlike the earlier versions
+(dplex, cdd+), it can deal with equations and totally zero right
+hand sides. It is recommended that {\tt solver} is
+{\tt dd\_DualSimplex}, the revised dual simplex method
+that updates a $d\times d$ dual basis matrix in each pivot (where
+$d$ is the column size of lp).
+
+The revised dual simplex method is ideal for dense LPs in small number of variables
+(i.e. small column size, typically less than $100$)
+and many inequality constraints (i.e. large row size, can be a few ten thousands).
+If your LP has many variables but only few constraints, solve the dual LP by
+this function.
+
+When it is compiled for GMP rational
+arithmetic, it first tries to solve an LP with C double
+floating-point arithmetic and verifies whether the output
+basis is correct with GMP. If so, the correct solution is
+computed with GMP. Otherwise, it (re)solves the LP
+from scratch with GMP. This is newly implemented
+in the version 093. The original (non-crossover) version of
+the same function is still available as {\tt boolean dd\_LPSolve0}.
+
+\item[{\tt dd\_boolean dd\_Redundant(matrix, i, point, err)}]:\\
+Check whether $i$th data in {\tt matrix} is redundant for the representation.
+If it is nonredundant, it returns a certificate. For H-representation,
+it is a {\tt point} in $R^d$ which satisfies
+all inequalities except for the $i$th inequality. If $i$ is a linearity,
+it does nothing and always returns {\tt dd\_FALSE}.
+
+\item[{\tt dd\_rowset dd\_RedundantRows(matrix, err)}]:\\
+Returns a maximal set of row indices such that the associated rows
+can be eliminated without changing the polyhedron.
+The function works for both V- and H-representations.
+
+\item[{\tt dd\_boolean dd\_SRedundant(matrix, i, point, err)}]:\\
+Check whether $i$th data in {\tt matrix} is strongly redundant for the representation.
+If $i$ is a linearity, it does nothing and always returns {\tt dd\_FALSE}.
+Here, $i$th inequality in H-representation is {\em strongly redundant\/} if it is redundant
+and there is no point in the polyhedron satisfying the inequality with equality.
+In V-representation, $i$th point is {\em strongly redundant\/} if it is redundant
+and it is in the relative interior of the polyhedron. If it is not strongly redundant, it returns a certificate.
+
+\item[{\tt dd\_boolean dd\_ImplicitLinearity(matrix, i, err)}]:\\
+Check whether $i$th row
+in the input is forced to be linearity (equality
+for H-representation).
+If $i$ is linearity itself,
+it does nothing and always returns {\tt dd\_FALSE}.
+
+\item[{\tt dd\_rowset dd\_ImplicitLinearityRows(matrix, err)}]:\\
+Returns the set of indices of rows that are
+implicitly linearity. It simply calls the library function
+{\tt dd\_ImplicitLinearity} for each inequality and collects
+the row indices for which the answer is {\tt dd\_TRUE}.
+
+\item[{\tt dd\_boolean dd\_MatrixCanonicalize(matrixP, impl\_lin, redset, newpos, err)}]:\\
+ The input is a pointer {\tt matrixP} to a matrix and the function
+modifies the matrix by putting a maximally linear independent linearities (basis)
+at the top of the matrix, and removing all redundant data.
+All implicit linearities and all (removed) redundant rows
+in the original matrix will be returned in the corresponding row sets.
+The new positions of the original rows are returned by
+the array {\tt newpos}.
+
+The cardinality of the new linearity set {\tt (*matrixP)->linset} is the codimension
+of the polyhedron if it is H-polyhedron, and is the dimension of linearity space
+if it is V-polyhedron.
+
+Note that the present version should not be called a canonicalization
+because it may generate two different representations of the same
+polyhedron. In the future, this function is expected to be correctly
+implemented.
+
+\item[{\tt dd\_boolean dd\_MatrixCanonicalizeLinearity(matrixP, impl\_linset, newpos. err)}]:\\
+It does only the first half of {\tt dd\_boolean dd\_MatrixCanonicalize}, namely, it detects all
+implicit linearities and puts a maximally independent linearities
+at the top of the matrix. For example, this function can be
+used to detect the dimension of an H-polyhedron.
+
+\item[{\tt dd\_boolean dd\_MatrixRedundancyRemove(matrixP, redset, newpos, err)}]:\\
+It does essentially the second half of {\tt dd\_boolean dd\_MatrixCanonicalize},
+namely, it detects all
+redundancies. This function should be used after {\tt dd\_MatrixCanonicalizeLinearity}
+has been called.
+
+
+\item[{\tt dd\_boolean dd\_FindRelativeInterior(matrix, impl\_lin, lin\_basis, lps, err)}]:\\
+Computes a point in the relative interior of an H-polyhedron given by matrix, by solving
+an LP. The point will be returned by {\tt lps}.
+See the sample program allfaces.c that generates all nonempty faces of an H-polyhedron and
+a relative interior point for each face. The former returns all implicit linearity rows (implicit equations)
+and the latter returns a basis of the union of linearity rows and implicit linearity rows.
+This means that the cardinality of {\tt *lin\_basis} is the codimension of the polyhedron.
+
+
+\item[{\tt dd\_boolean dd\_ExistsRestrictedFace(matrix, R, S, err)}]:\\
+Returns the answer to the Farkas' type decision problem as to whether there is a point
+in the polyhedron given by matrix satisfying all constraints in {\tt R} with
+equality and all constraints in {\tt S} with strict inequality. More precisely,
+it is the linear feasibility problem:
+\[
+\begin{array}{llllll}
+\exists\mbox{?} &x &\mbox{ satisfying } & b_r - A_r x &= 0, \; \forall r \in R\cup L \\
+ & & & b_s - A_s x &> 0, \; \forall s \in S \\
+ & & & b_t - A_t x &\ge 0, \; \forall t \in T,
+\end{array}
+\]
+where $L$ is the set of linearity rows of {\tt matrix}, and $T$ represents
+the set of rows that are not in $R\cup L \cup S$.
+Both {\tt R} and {\tt S} are of {\tt dd\_rowset} type. The set $S$ is
+supposed to be disjoint from both $R$ and $L$.
+If it is not the case, the set $S$ will be considered as $S \setminus (R \cup L)$.
+
+This function ignores {\tt matrix->representation}, and thus even if it is
+set to {\tt dd\_Generator} or {\tt dd\_Unspecified}, it treats the matrix
+as if it were inequality representation.
+
+\item[{\tt dd\_boolean dd\_ExistsRestrictedFace2(matrix, R, S, lps, err)}]:\\
+It is the same as the function {\tt dd\_ExistsRestrictedFace} except that
+it returns also a certificate for the answer. The certificate is a solution
+to the bounded LP:
+\[
+\begin{array}{lllllll}
+\mbox{(P)} &\max z &\mbox{ subject to } & b_r - A_r x & & = 0, \; \forall r \in R\cup L \\
+ & & & b_s - A_s x &-z &\ge 0, \; \forall s \in S \\
+ & & & b_t - A_t x & &\ge 0, \; \forall t \in T \\
+ & & & 1 & -z&\ge 0,
+\end{array}
+\]
+where $L$ is the set of linearity rows of {\tt matrix}, and $T$ represents
+the set of rows that are not in $R\cup L \cup S$.
+The answer for the decision problem is YES if and only if the LP attains
+an optimal and the optimal value is positive. The dual solution (either
+an optimal solution or a dual unbounded direction) can be considered
+as a certificate for the NO answer, if the answer is NO.
+
+This function ignores {\tt matrix->representation}, and thus even if it is
+set to {\tt dd\_Generator} or {\tt dd\_Unspecified}, it treats the matrix
+as if it were inequality representation.
+
+\item[{\tt dd\_SetFamilyPtr dd\_Matrix2Adjacency(matrix, err)}]:\\
+Computes the adjacency list of input rows using
+the LP solver and without running the representation conversion. When
+the input is H-representation, it gives the facet graph of the polyhedron.
+For V-representation, it gives the (vertex) graph of the polyhedron.
+It is required that the input matrix is a minimal representation.
+Run redundancy removal functions before calling this function,
+see the sample code adjacency.c.
+
+
+\item[{\tt dd\_SetFamilyPtr dd\_Matrix2WeakAdjacency(matrix, err)}]:\\
+Computes the weak adjacency list of input rows using
+the LP solver and without running the representation conversion. When
+the input is H-representation, it gives the graph where its nodes are the facets
+two nodes are adjacent if and only if the associated facets have
+some intersection.
+For V-representation, it gives the graph where its nodes are the vertices
+and two nodes are adjacent if and only if the associated vertices
+are on a common facet.
+It is required that the input matrix is a minimal representation.
+Run redundancy removal functions before calling this function,
+see the sample code adjacency.c.
+
+\item[{\tt dd\_MatrixPtr dd\_FourierElimination(matrix, err)}]:\\
+Eliminate the last variable from a system of linear inequalities
+given by matrix by using the Fourier's Elimination. If the
+input matrix is V-representation, {\tt *err} returns
+{\tt dd\_NotAvailForV}. This function does not
+remove redundancy and one might want to call
+redundancy removal functions afterwards. See the sample code fourier.c.
+
+\item[{\tt dd\_MatrixPtr dd\_BlockElimination(matrix, set, err)}]:\\
+Eliminate a set of variables from a system of linear inequalities
+given by matrix by using the extreme rays of the dual linear system.
+See comments in the code cddproj.c for details. This might be
+a faster way to eliminate variables than the repeated FourierElimination when
+the number of variables to eliminate is large.
+If the input matrix is V-representation, {\tt *err} returns {\tt dd\_NotAvailForV}.
+This function does not remove redundancy and one might want to call
+redundancy removal functions afterwards. See the sample code projection.c.
+
+
+\item[{\tt dd\_rowrange dd\_RayShooting(matrix, point, vector)}]:\\
+Finds the index of a halfspace first left by the ray starting from
+{\tt point} toward the direction {\tt vector}. It resolves
+tie by a lexicographic perturbation. Those inequalities violated
+by {\tt point} will be simply ignored.
+
+\end{description}
+
+
+\subsection{Data Manipulations} \label{DataLibrary}
+
+\subsubsection{Number Assignments}
+For number assignments, one cannot use such expressions as {\tt x=(mytype)a}.
+This is because cddlib uses an abstract number type ({\tt mytype})
+so that it can compute with various
+number types such as C double and GMP rational.
+User can easily add a new number type by redefining
+arithmetic operations in cddmp.h and cddmp.c.
+
+\begin{description}
+
+
+\item[{\tt void dd\_init(x)}]:\\
+This is to initialize a {\tt mytype} variable {\tt x} and to set it
+to zero. This initialization has to be called before
+any {\tt mytype} variable to be used.
+
+\item[{\tt void dd\_clear(x)}]:\\
+This is to free the space allocated to a {\tt mytype} variable {\tt x}.
+
+\item[{\tt void dd\_set\_si(x, a)}]:\\
+This is to set a {\tt mytype} variable {\tt x} to the
+value of signed long integer {\tt a}.
+
+\item[{\tt void dd\_set\_si2(x, a, b)}]:\\
+This is to set a {\tt mytype} variable {\tt x} to the
+value of the rational expression {\tt a/b}, where
+{\tt a} is signed long and {\tt b} is unsigned long
+integers.
+
+\item[{\tt void dd\_set\_d(x, b)}]:\\
+This is to set a {\tt mytype} variable {\tt x} to the
+value of double {\tt b}. This is available only
+when the library is compiled without {\tt -DGMPRATIONAL}
+compiler option.
+
+\end{description}
+
+
+\subsubsection{Arithmetic Operations for {\tt mytype} Numbers}
+
+Below {\tt x}, {\tt y}, {\tt z} are of type {\tt mytype}.
+
+\begin{description}
+
+\item[{\tt void dd\_add(x, y, z)}]:\\
+Set {\tt x} to be the sum of {\tt y} and {\tt z}.
+
+\item[{\tt void dd\_sub(x, y, z)}]:\\
+Set {\tt x} to be the substraction of {\tt z} from {\tt y}.
+
+\item[{\tt void dd\_mul(x, y, z)}]:\\
+Set {\tt x} to be the multiplication of {\tt y} and {\tt z}.
+
+\item[{\tt void dd\_div(x, y, z)}]:\\
+Set {\tt x} to be the division of {\tt y} over {\tt z}.
+
+\item[{\tt void dd\_inv(x, y)}]:\\
+Set {\tt x} to be the reciplocal of {\tt y}.
+
+\end{description}
+
+
+\subsubsection{Predefined Constants} \label{constants}
+
+There are several {\tt mytype} constants defined when {\tt dd\_set\_global\_constants(void)} is called.
+Some constants depend on the double constant {\tt dd\_almostzero} which is normally set to $10^{-7}$ in cdd.h.
+This value can be modified depending on how numerically delicate your problems are but an extra
+caution should be taken.
+
+\begin{description}
+
+\item[{\tt mytype dd\_purezero}]:\\
+This represents the mathematical zero $0$.
+
+\item[{\tt mytype dd\_zero}]:\\
+This represents the largest positive number which should be considered to be zero. In the GMPRATIONAL
+mode, it is equal to {\tt dd\_purezero}. In the C double mode, it is set to the value of {\tt dd\_almostzero}.
+
+\item[{\tt mytype dd\_minuszero}]:\\
+The negative of {\tt dd\_zero}.
+
+\item[{\tt mytype dd\_one}]:\\
+This represents the mathematical one $1$.
+
+
+\end{description}
+
+\subsubsection{Sign Evaluation and Comparison for {\tt mytype} Numbers}
+
+Below {\tt x}, {\tt y}, {\tt z} are of type {\tt mytype}.
+
+\begin{description}
+
+\item[{\tt dd\_boolean dd\_Positive(x)}]:\\
+Returns {\tt dd\_TRUE} if {\tt x} is considered positive, and {\tt dd\_FALSE} otherwise.
+In the GMPRATIONAL mode, the positivity recognition is exact. In the C double mode,
+this means the value is strictly larger than {\tt dd\_zero}.
+
+{\tt dd\_boolean dd\_Negative(x)} works similarly.
+
+\item[{\tt dd\_boolean dd\_Nonpositive(x)}]:\\
+Returns the negation of {\tt dd\_Positive(x)}. {\tt dd\_Nonnegative(x)} works similarly.
+
+\item[{\tt dd\_boolean dd\_EqualToZero(x)}]:\\
+Returns {\tt dd\_TRUE} if {\tt x} is considered zero, and {\tt dd\_FALSE} otherwise.
+In the GMPRATIONAL mode, the zero recognition is exact. In the C double mode,
+this means the value is inbetween {\tt dd\_minuszero} and {\tt dd\_zero}
+inclusive.
+
+\item[{\tt dd\_boolean dd\_Larger(x, y)}]:\\
+Returns {\tt dd\_TRUE} if {\tt x} is strictly larger than {\tt y}, and {\tt dd\_FALSE} otherwise.
+This is implemented as {dd\_Positive(z)} where {\tt z} is the subtraction of {\tt y}
+from {\tt x}.
+{\tt dd\_Smaller(x, y)} works similarly.
+
+\item[{\tt dd\_boolean dd\_Equal(x, y)}]:\\
+Returns {\tt dd\_TRUE} if {\tt x} is considered equal to {\tt y}, and {\tt dd\_FALSE} otherwise.
+This is implemented as {dd\_EqualToZero(z)} where {\tt z} is the subtraction of {\tt y}
+from {\tt x}.
+\end{description}
+
+
+
+\subsubsection{Polyhedra Data Manipulation}
+\begin{description}
+
+\item[{\tt dd\_MatrixPtr dd\_PolyFile2Matrix (f, err)}]:\\
+Read a Polyhedra data from stream {\tt f} and store it in {\tt matrixdata}
+and return a pointer to the data.
+
+\item[{\tt dd\_MatrixPtr dd\_CopyInequalities(poly)}]:\\
+Copy the inequality representation pointed by poly to {\tt matrixdata}
+and return {\tt dd\_MatrixPtr}.
+
+\item[{\tt dd\_MatrixPtr dd\_CopyGenerators(poly)}]:\\
+Copy the generator representation pointed by poly to {\tt matrixdata}
+and return {\tt dd\_MatrixPtr}.
+
+\item[{\tt dd\_SetFamilyPtr dd\_CopyIncidence(poly)}]:\\
+Copy the incidence representation of the computed representation
+pointed by poly to {\tt setfamily}
+and return {\tt dd\_SetFamilyPtr}. The computed representation is
+{\tt Inequality} if the input is {\tt Generator}, and the vice visa.
+
+\item[{\tt dd\_SetFamilyPtr dd\_CopyAdjacency(poly)}]:\\
+Copy the adjacency representation of the computed representation
+pointed by poly to {\tt setfamily}
+and return {\tt dd\_SetFamilyPtr}. The computed representation is
+{\tt Inequality} if the input is {\tt Generator}, and the vice visa.
+
+\item[{\tt dd\_SetFamilyPtr dd\_CopyInputIncidence(poly)}]:\\
+Copy the incidence representation of the input representation
+pointed by poly to {\tt setfamily}
+and return {\tt d\_SetFamilyPtr}.
+
+\item[{\tt dd\_SetFamilyPtr dd\_CopyInputAdjacency(poly)}]:\\
+Copy the adjacency representation of the input representation
+pointed by poly to {\tt setfamily}
+and return {\tt d\_SetFamilyPtr}.
+
+\item[{\tt void dd\_FreePolyhedra(poly)}]:\\
+Free memory allocated to {\tt poly}.
+
+\end{description}
+
+\subsubsection{LP Data Manipulation}
+\begin{description}
+
+\item[{\tt dd\_LPPtr dd\_MakeLPforInteriorFinding(lp)}]:\\
+Set up an LP to find an interior point of the feasible region of {\tt lp}
+and return a pointer to the LP. The new LP has one new variable
+$x_{d+1}$ and one more constraint:
+$\max x_{d+1}$ subject to $b - A x - x_{d+1} \ge 0$ and $x_{d+1} \le K$,
+where $K$ is a positive constant.
+
+\item[{\tt dd\_LPPtr dd\_Matrix2LP(matrix, err)}]:\\
+Load {\tt matrix} to {\tt lpdata} and return a pointer to the data.
+
+\item[{\tt dd\_LPSolutionPtr dd\_CopyLPSolution(lp)}]:\\
+Load the solutions of {\tt lp} to {\tt lpsolution} and
+return a pointer to the data. This replaces the old name
+{\tt dd\_LPSolutionLoad(lp)}.
+
+\item[{\tt void dd\_FreeLPData(lp)}]:\\
+Free memory allocated as an LP data pointed by {\tt lp}.
+
+\item[{\tt void dd\_FreeLPSolution(lps)}]:\\
+Free memory allocated as an LP solution data pointed by {\tt lps}.
+
+\end{description}
+
+\subsubsection{Matrix Manipulation}
+\begin{description}
+
+\item[{\tt dd\_MatrixPtr dd\_CopyMatrix(matrix)}]:\\
+Make a copy of matrixdata pointed by {\tt matrix} and return
+a pointer to the copy.
+
+\item[{\tt dd\_MatrixPtr dd\_AppendMatrix(matrix1, matrix2)}]:\\
+Make a matrixdata by copying {\tt *matrix1} and appending
+the matrix in {\tt *matrix2} and return
+a pointer to the data. The colsize must be equal in
+the two input matrices. It returns a {\tt NULL} pointer
+if the input matrices are not appropriate.
+Its {\tt rowsize} is set to
+the sum of the rowsizes of {\tt matrix1} and {\tt matrix2}.
+ The new matrixdata inherits everything else
+(i.e. numbertype, representation, etc)
+from the first matrix.
+
+\item[{\tt int dd\_MatrixAppendTo(\& matrix1, matrix2)}]:\\
+Same as {\tt dd\_AppendMatrix} except that the first matrix
+is modified to take the result.
+
+\item[{\tt int dd\_MatrixRowRemove(\& matrix, i)}]:\\
+Remove the $i$th row of {\tt matrix}.
+
+\item[{\tt dd\_MatrixPtr dd\_MatrixSubmatrix(matrix, set)}]:\\
+Generate the submatrix of {\tt matrix} by removing the
+rows indexed by {\tt set} and return a matrixdata pointer.
+
+\item[{\tt dd\_SetFamilyPtr dd\_Matrix2Adjacency(matrix, err)}]:\\
+Return the adjacency list of the representation given by {\tt matrix}.
+The computation is done by the built-in LP solver. The representation
+should be free of redundancy when this function is called.
+See the function {\tt dd\_rowset dd\_RedundantRows}
+and the example program adjacency.c.
+
+\end{description}
+
+\subsection{Input/Output Functions} \label{IOLibrary}
+
+\begin{description}
+
+\item[{\tt dd\_MatrixPtr dd\_PolyFile2Matrix (f, err)}]:\\
+Read a Polyhedra data from stream {\tt f} and store it in {\tt matrixdata}
+and return a pointer to the data.
+
+\item[{\tt boolean dd\_DDFile2File(ifile, ofile, err)}]:\\
+Compute the representation conversion for a polyhedron given
+by a Polyhedra file ifile, and write the other representation
+in a Polyhedra file ofile. {\tt *err}
+returns {\tt dd\_NoError} if the computation terminates normally. Otherwise,
+it returns a value according to the error occured.
+
+\item[{\tt void dd\_WriteMatrix(f, matrix)}]:\\
+Write {\tt matrix} to stream {\tt f}.
+
+\item[{\tt void dd\_WriteNumber(f, x)}]:\\
+Write {\tt x} to stream {\tt f}. If {\tt x} is of GMP mpq\_t rational $p/q$,
+the output is $p/q$. If it is of C double, it is formated as a double float
+with a decimal point.
+
+\item[{\tt void dd\_WritePolyFile(f, poly)}]:\\
+Write {tt poly} to stream {\tt f} in Polyhedra format.
+
+\item[{\tt void dd\_WriteErrorMessages(f, err)}]:\\
+Write error messages given by {\tt err} to stream {\tt f}.
+
+\item[{\tt void dd\_WriteSetFamily(f, setfam)}]:\\
+Write the set family pointed by {\tt setfam} to stream {\tt f}.
+For each set, it outputs its index, its cardinality,
+a colon ``:'' and a ordered list of its elements.
+
+\item[{\tt void dd\_WriteSetFamilyCompressed(f, setfam)}]:\\
+Write the set family pointed by {\tt setfam} to stream {\tt f}.
+For each set, it outputs its index, its cardinality or the
+negative of the cardinality, a colon ``:''
+ and the elements in the set or its complements whichever is smaller.
+Whenever it outputs the complements, the cardinality is negated
+so that there is no ambiguity.
+This will be considered standard for
+outputing incidence (*.icd, *ecd) and adjacency
+(*.iad, *.ead) data in cddlib. But there is some minor incompatibility
+with cdd/cdd+ standalone codes.
+
+\item[{\tt void dd\_WriteProgramDescription(f)}]:\\
+Write the cddlib version information to stream {\tt f}.
+
+\item[{\tt void dd\_WriteDDTimes(f, poly)}]:\\
+Write the representation conversion time information on {\tt poly}
+ to stream {\tt f}.
+
+\end{description}
+
+\subsection{Obsolete Functions} \label{ObsoleteFunctions}
+\begin{description}
+\item[{\tt boolean dd\_DoubleDescription(poly, err)}]:
+(removed in Version 0.90c)\\
+The new function
+{\tt dd\_DDMatrix2Poly(matrix, err)} (see Section~\ref{CoreLibrary})
+replaces (and actually combines) both this and
+{\tt dd\_Matrix2Poly(matrix, err)}.
+
+\item[{\tt dd\_PolyhedraPtr dd\_Matrix2Poly(matrix, err)}]:
+(removed in Version 0.90c)\\
+See above for the reason for removal.
+
+\item[{\tt dd\_LPSolutionPtr dd\_LPSolutionLoad(lp)}]:
+(renamed in Version 0.90c)\\
+This function is now called {\tt dd\_CopyLPSolution(lp)}.
+
+\end{description}
+
+
+\subsection{Set Functions in {\tt setoper} library} \label{SetFunctions}
+
+The cddlib comes with a simple set operation library {\tt setoper}. The key
+type defined is {\tt set\_type}. A set is represented by a fixed length
+binary strings. Thus, the maximum length of a set must be declared when
+it is initialized.
+
+Below the symbols {\tt a}, {\tt b}, {\tt c} are
+of type {\tt set\_type}. The symbols {\tt aP} is a
+pointer to type {\tt set\_type}, and {\tt s}, {\tt t} are of type {\tt long}.
+Here are some of the functions defined. See {\tt setoper.h} for a
+complete listing.
+
+\begin{description}
+
+\item[{\tt void set\_initialize(aP, s)}]:\\
+Allocate a {\tt set\_type} space of maximum cardinality {\tt s}
+ and make it pointed by {\tt aP}. The set is initialized as empty set.
+
+\item[{\tt void set\_free(a)}]:\\
+Free the {\tt set\_type} space allocated for {\tt a}.
+
+\item[{\tt void set\_copy(a, b))}]:\\
+Set {\tt a} to be {\tt b}. The set {\tt a} must be pre-initialized
+with the same maximum cardinality as that of {\tt b}.
+
+\item[{\tt void set\_addelem(a, t))}]:\\
+Add an element {\tt t} to a set {\tt a}. The set {\tt a} stays unchanged
+if it contains the element {\tt t}.
+
+\item[{\tt long set\_card(a))}]:\\
+Return the cardinality of set {\tt a}.
+
+\item[{\tt int set\_member(t, a))}]:\\
+Return $1$ if {\tt t} is a member of set {\tt a}, and $0$ otherwise.
+
+
+\item[{\tt void set\_write(a))}]:\\
+Print out the elements of set {\tt a} to {\tt stdout}. The function {\tt void set\_fwrite(f, a))} output
+to stream {\tt f}.
+
+\end{description}
+
+\section{An Extension of the CDD Library in GMP mode} \label{GMPLIB}
+
+Starting from the version 093, the GMP version of cddlib, {\tt libcddgmp.a}, contains
+all cdd library functions in two arithmetics. All functions with the standard prefix {\tt dd\_}
+are computed with the GMP rational arithmetic as before. The same fuctions with
+the new prefix {\tt ddf\_} are now added to the library {\tt libcddgmp.a} that are based
+on the C double floating-point arithmetic. Thus these functions are equivalent to
+ {\tt libcdd.a} functions, except that all functions and variable types are with prefix {\tt ddf\_} and
+the variable type {\tt mytype} is replaced by {\tt myfloat}.
+
+In this sense, {\tt libcdd.a} is a proper subset of {\tt libcddgmp.a} and in principle one can
+do everything with {\tt libcddgmp.a}. See how the new {\tt dd\_LPSolve} is written in
+cddlp.c.
+
+
+\section{Examples} \label{EXAMPLES}
+
+See example codes such as testcdd*.c , testlp*.c, redcheck.c, adjacency.c, allfaces,c
+and simplecdd.c
+in the {\tt src} and {\tt src-gmp} subdirectories of the source
+distribution.
+
+\section{Numerical Accuracy} \label{accuracy}
+ A little caution is in order. Many people have observed
+numerical problems of cddlib when the floating version of cddlib
+is used. As we all know, floating-point computation
+might not give a correct answer, especially when an input
+data is very sensitive to a small perturbation. When
+some strange behavior is observed, it is always wise
+to create a rationalization of the input
+(for example, one can replace 0.3333333 with 1/3)
+and to compute it with cddlib compiled with gmp rational
+to see what a correct behavior should be. Whenever the time
+is not important, it is safer to use gmp rational arithmetic.
+
+If you need speedy computation with floating-point arithmetic,
+you might want to ``play with'' the constant {\tt dd\_almostzero}
+defined in cdd.h:
+
+\begin{verbatim}
+ #define dd_almostzero 1.0E-7
+\end{verbatim}
+\noindent
+This number is used to recognize whether a number is zero:
+a number whose absolute value is smaller
+than {\tt dd\_almostzero} is considered zero, and nonzero otherwise.
+You can change this to modify the behavior of cddlib. One might
+consider the default setting is rather large for double
+precision arithmetic. This is because cddlib is made
+to deal with highly degenerate data and it works better
+to treat a relatively large ``epsilon'' as zero.
+
+Another thing one can do is scaling. If the values in one column of
+an input is of smaller magnitude than those in another column,
+scale one so that they become comparable.
+
+\section{Other Useful Codes} \label{CODES}
+There are several other useful codes available for vertex enumeration and/or
+convex hull computation such as lrs, qhull, porta and irisa-polylib.
+The pointers to these codes are available at
+\begin{enumerate}
+\item lrs by D. Avis \cite{a-lrshome-01} (C implementation of the reverse search algorithm
+\cite{af-pachv-92}).
+
+\item qhull by C.B. Barber \cite{bdh-qach-03} (C implementation of
+the beneath-beyond method, see \cite{e-acg-87,m-cg-94},
+which is the dual of the dd method).
+
+\item porta by T. Christof and A. L{\"o}bel \cite{cl-porta-97} (C implementation
+of the Fourier-Motzkin elimination).
+
+\item IRISA polyhedral library by D.K. Wilde
+\cite{w-ldpo-93b} (C implementation
+of a variation of the dd algorithm).
+
+\item PPL: the Parma Polyhedra Library \cite{b-pplhome} by R. Bagnara (C++ implementation of
+a variation of the dd algorithm).
+
+\item {\tt pd} by A. Marzetta \cite{m-pdcip-97} (C implementation of the primal-dual algorithm
+\cite{bfm-pdmvf-97}).
+
+ \item Geometry Center Software List by N. Amenta \cite{a-dcg}.
+
+ \item Computational Geometry Pages by J. Erickson \cite{e-cgp}.
+
+ \item Linear Programming FAQ by R. Fourer and J. Gregory \cite{fg-lpfaq}.
+
+ \item ZIB Berlin polyhedral software list:\\
+ \htmladdnormallink{ftp://elib.zib-berlin.de/pub/mathprog/polyth/index.html}
+{ftp://elib.zib-berlin.de/pub/mathprog/polyth/index.html}.
+
+
+\item Polyhedral Computation FAQ \cite{f-pcfaq-98}.
+\end{enumerate}
+
+\section{Codes Using Cddlib} \label{USERCODES}
+
+There are quite a few nice programs using some functions of cddlib.
+Here are some of them.
+
+
+\begin{enumerate}
+
+\item {\tt LattE} \cite{dhhhty-latte-05} computes the number of lattice points
+in a convex polytope.
+
+\item {\tt Minksum} \cite{w-msv-05} is a program to compute the V-representation
+(i.e. the set of vertices) of the Minkowski addition of several convex polytopes
+given by their V-representation in $\R^d$. It is an implementation in C++ language
+of the reverse search algorithm \cite{f-fzctmacp-04} whose time complexity is
+polynomially bounded by the sizes of input and output.
+
+\item {\tt Gfan} \cite{j-gvum-05} is a program to list all reduced Gr\"obner
+bases of a general polynomial ideal given by a set of generating polynomials
+in $n$-variables. It is an implementation in C++ language
+of the reverse search algorithm \cite{fjt-cgf-05}.
+
+
+\item {\tt TOPCOM} \cite{r-topcom-05} computes the combinatorial structure
+(the oriented matroid) of a point configuration and enumerates all triangulations
+of a point set. It detects the regularlity of a triangulation using cddlib.
+
+\end{enumerate}
+
+
+\section*{Acknowledgements.}
+I am grateful to Tom Liebling who
+provided me with an ideal opportunity to visit EPFL
+for the academic year 1993-1994. Later, Hans-Jakob L\"uthi (ETHZ) and
+Emo Welzl (ETHZ) joined to support the
+the development of cdd codes (cdd, cdd+, cddlib).
+Without their generous and continuing support, the present form of
+this program would not have existed.
+
+There are many other people who helped me to improve cdd, in particular,
+I am indebted to David Avis,
+Alexander Bockmayr, David Bremner, Henry Crapo, Istvan Csabai,
+Francois Margot, Marc Pfetsch, Alain Prodon, J\"org Rambau, Dima Pasechnik,
+Shawn Rusaw, Matthew Saltzman, Masanori Sato, Anders Jensen,
+Ruriko Yoshida, Charles Geyer, Michal Kvasnica, Sven Verdoolaege
+ (listed in arbitrary order) and those listed
+in the HISTORY file.
+
+\bibliographystyle{plain}
+
+\bibliography{fukuda1,fukuda2}
+
+\end{document}
+
+