Core Functions

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 dd_DD*. The second type solves an linear program and the standard naming is dd_LP*. Both 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.

dd_PolyhedraPtr dd_DDMatrix2Poly(matrix, err)

:
Store the representation given by matrix in a polyhedra data, and generate the second representation of *poly. It returns a pointer to the data. *err returns dd_NoError if the computation terminates normally. Otherwise, it returns a value according to the error occured.

dd_PolyhedraPtr dd_DDMatrix2Poly2(matrix, roworder, err)

:
This is the same function as dd_DDMatrix2Poly except that the insertion order is specified by the user. The argument roworder is of dd_RowOrderType and takes one of the values: dd_MaxIndex, dd_MinIndex, dd_MinCutoff, dd_MaxCutoff, dd_MixCutoff, dd_LexMin, dd_LexMax, dd_RandomRow. In general, dd_LexMin is the best choice which is in fact chosen in dd_DDMatrix2Poly. If you know that the input is already sorted in the order you like, use dd_MinIndex or dd_MaxIndex. If the input contains many redundant rows (say more than $80\%$ redundant), you might want to try dd_MaxCutoff which might result in much faster termination, see [3,12]

boolean dd_DDInputAppend(poly, matrix, err)

:
Modify the input representation in *poly by appending the matrix of *matrix, and compute the second representation. The number of columns in *matrix must be equal to the input representation.

boolean dd_LPSolve(lp, solver, err)

:
Solve lp by the algorithm solver and save the solututions in *lp. Unlike the earlier versions (dplex, cdd+), it can deal with equations and totally zero right hand sides. It is recommended that solver is 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 arithmetics, it first tries to solve an LP with C double floating-point arithmetics 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 boolean dd_LPSolve0.

dd_boolean dd_Redundant(matrix, i, point, err)

:
Check whether $i$th data in matrix is redundant for the representation. If it is nonredundant, it returns a certificate. For H-representation, it is a 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 dd_FALSE.

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.

dd_boolean dd_SRedundant(matrix, i, point, err)

:
Check whether $i$th data in matrix is strongly redundant for the representation. If $i$ is a linearity, it does nothing and always returns dd_FALSE. Here, $i$th inequality in H-representation is 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 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.

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

dd_rowset dd_ImplicitLinearityRows(matrix, err)

:
Returns the set of indices of rows that are implicitly linearity. It simply calls the library function dd_ImplicitLinearity for each inequality and collects the row indices for which the answer is dd_TRUE.

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.

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.

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, *err returns dd_NotAvailForV. This function does not remove redundancy and one might want to call redundancy removal functions afterwards. See the sample code fourier.c.

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, *err returns dd_NotAvailForV. This function does not remove redundancy and one might want to call redundancy removal functions afterwards. See the sample code projection.c.

dd_rowrange dd_RayShooting(matrix, point, vector)

:
Finds the index of a halfspace first left by the ray starting from point toward the direction vector. It resolves tie by a lexicographic perturbation. Those inequalities violated by point will be simply ignored.