third_party/cddlib/doc/cddlibman.tex

% 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}