The cdd module

Enums

class cdd.LPObjType(value)

Bases: IntEnum

Objective for a linear program.

NONE

MAX

MIN

class cdd.LPSolverType(value)

Bases: IntEnum

Solver for a linear program.

CRISS_CROSS

DUAL_SIMPLEX

class cdd.LPStatusType(value)

Bases: IntEnum

Status of a linear program.

UNDECIDED

OPTIMAL

INCONSISTENT

DUAL_INCONSISTENT

STRUC_INCONSISTENT

STRUC_DUAL_INCONSISTENT

UNBOUNDED

DUAL_UNBOUNDED

class cdd.RepType(value)

Bases: IntEnum

Representation. Use INEQUALITY for H-representation and GENERATOR for V-representation.

UNSPECIFIED

INEQUALITY

GENERATOR

class cdd.RowOrderType(value)

Bases: IntEnum

Row order for the double description method.

MAX_INDEX

MIN_INDEX

MIN_CUTOFF

MAX_CUTOFF

MIX_CUTOFF

LEX_MIN

LEX_MAX

RANDOM_ROW

Classes

class cdd.Matrix

A set of inequalities/equalities (H-representation) or a set of non-linear/linear generators (V-representation) described by an array \([b \quad A]\) and a row index set \(L\).

For this class, rep_type determines the representation type, array determines the array \([b \quad A]\), and lin_set determines the row index set \(L\).

The H-representation corresponds to a polyhedron \(P\) formed by all points \(x\) satisfying

\[\begin{split}0&\le b_i + A_i x \qquad \forall i\notin L \\ 0&= b_i + A_i x \qquad \forall i\in L \\\end{split}\]

where \(A_i\) denotes the \(i\)-th row of \(A\).

To understand the V-representation, first we need the concept of a halfspace. For any real number \(z_0\) and column vector \(z\), we define a halfspace as follows:

\[H_{z_0,z}^{\ge}=\{x\colon z_0+x^T z\ge 0\}\]

Note that \(z\) is allowed to be the zero vector, in which case the halfspace is either the complete space (if \(z_0\ge 0\)) or the empty space (if \(z_0<0\)).

The V-representation corresponds to the polyhedron formed by the intersection of all halfspaces \(H_{z_0,z}^{\ge}\) satisfying

\[\begin{split}0&\le b_i z_0 + A_i z \qquad \forall i\notin L \\ 0&= b_i z_0 + A_i z \qquad \forall i\in L\end{split}\]

A halfspace that satisfies these constraints is called feasible. The set of feasible halfspaces forms a convex cone, denoted \(Z\), in the \((z_0,z)\)-space. This cone has a dual:

\[Z^*=\{(x_0,x)\colon x_0z_0+x^Tz\ge 0\, \forall z\in Z\}\]

In other words, the polyhedron described by the V-representation is the intersection of the dual cone \(Z^*\) and the hyperplane determined by \(x_0=1\):

\[P=Z^*\cap\{(x_0,x)\colon x_0=1\}\]

To make this easier to visualize, by convention, each equation is divided by \(b_i\) if \(b_i\neq 0\), i.e.

\[\begin{split}[t_i \quad V_i]= \begin{cases} [0 \quad A_i]\text{ if }b_i=0 \\ [1 \quad A_i/b_i]\text{ if }b_i\neq 0 \end{cases}\end{split}\]

This then leads to an array \([t \quad V]\), representing the same polyhedron \(P\) as \([b \quad A]\): indeed, \(H_{z_0,z}^{\ge}\) is feasible if and only if

\[\begin{split}0\le t_i z_0 + V_i z \qquad &\forall i\notin L \\ 0= t_i z_0 + V_i z \qquad &\forall i\in L\end{split}\]

For any point of the form \(x=\sum_i \lambda_i V_i^T\), with \(\sum_i \lambda_i t_i=1\) and \(\lambda_i\ge 0\) for all \(i\notin L\), we have that \(x\) belongs to the polyhedron, because in that case

\[\begin{split}z_0+x^T z &= z_0 + \sum_i \lambda_i V_i z \\ &=\sum_i \lambda_i (t_i z_0 + V_i z) &\ge 0\end{split}\]

It can be shown that this describes the entire polyhedron, i.e. the polyhedron in the V-representation is the set of points

\[P=\left\{ \sum_i \lambda_i V_i\colon \sum_{i} \lambda_i t_i=1 \text{ and } \forall i\notin L\colon\lambda_i\ge 0 \right\}\]

For this reason, the \(V_i\) are called the generators of the polyhedron. By the Minkowski-Weyl theorem, without loss of generality, it can be assumed that \(i\notin L\) whenever \(t_i=1\). In that case,

\[P= \mathrm{conv}\{V_i\colon t_i=1\} +\mathrm{span}_{\ge}\{V_i\colon t_i=0,i\not\in L\} +\mathrm{span}\{V_i\colon t_i=0,i\in L\}\]

where \(\mathrm{conv}\) is the convex hull operator, \(\mathrm{span}_{\ge}\) is the linear span operator with non-negative coefficients, and \(\mathrm{span}\) is the linear span operator with free coefficients.

The library will always output V-representations in this form, i.e. so that all components of the first column are zero or one, and so that \(L\) does not contain rows whose first component is one.

array: Sequence[Sequence[float]]

Array representing the inequalities or generators.

lin_set: Set[int]

A set containing the rows of linearity. These are linear generators for the V-representation, and equalities for the H-representation.

obj_func: Sequence[float]

Linear programming objective function.

obj_type: LPObjType

Linear programming objective: maximize, minimize, or none.

rep_type: RepType

Representation: inequalities (H-representation), generators (V-representation), or unspecified.

class cdd.LinProg

A linear program: a set of inequalities and an objective function to optimize.

array: Sequence[Sequence[float]]

The array representing the linear program. More specifically, the constraints \(0\le b+Ax\) and objective function \(\gamma + c^T x\) are stored as an array as follows:

\[\begin{split}\begin{array}{cc} b & A \\ \gamma & c \end{array}\end{split}\]

i.e. the constraints are stored as a H-representation (with inequalities only), and the objective function is stored in the final row. Only inequality constraints are represented. Equality constraints can be represented by two opposing inequalities.

dual_solution: Sequence[tuple[int, float]]

The optimal value of the dual variables, after solving. Only the non-basic components are given (the basic components are zero). They are returned as index-value pairs.

obj_type: LPObjType

Whether we are minimizing or maximizing.

obj_value: float

The optimal value of the objective function, after solving.

primal_solution: Sequence[float]

The optimal value of the primal variables, after solving.

solver: LPSolverType

The solver used when last solving the linear program.

status: LPStatusType

The status of the linear program, after solving.

class cdd.Polyhedron

Representation of a polyhedron.

rep_type: RepType

Representation type of the input.

Factories

cdd.matrix_from_array(array: Sequence[Sequence[SupportsFloat]], lin_set: Container[int] = (), rep_type: RepType = RepType.UNSPECIFIED, obj_type: LPObjType = LPObjType.NONE, obj_func: Sequence[SupportsFloat] | None = None) → Matrix

Construct a matrix with the given attributes.

See cdd.Matrix.array for an explanation of how array must be laid out. This function also accepts 2-dimensional numpy arrays.

cdd.linprog_from_array(array: Sequence[Sequence[SupportsFloat]], obj_type: LPObjType) → LinProg

Construct a linear program from array.

See cdd.LinProg.array for an explanation of how array must be laid out. This function also accepts 2-dimensional numpy arrays.

Added in version 3.0.0.

cdd.linprog_from_matrix(mat: Matrix) → LinProg

Convert mat into a linear program. Note that mat must have the H-representation, and its objective type must be set, otherwise a ValueError is raised.

cdd.polyhedron_from_matrix(mat: Matrix, row_order: RowOrderType | None = None) → Polyhedron

Run the double description method to convert mat into a polyhedron, using row_order if specified.

Added in version 3.0.0: The row_order parameter.

Basic Operations

cdd.matrix_append_to(mat1: Matrix, mat2: Matrix) → None

Append mat2 to mat1.

A ValueError is raised if the column sizes are unequal.

cdd.matrix_copy(mat: Matrix) → Matrix

Return a copy of mat.

cdd.matrix_rank(mat: Matrix, ignored_rows: Container[int] = (), ignored_cols: Container[int] = ()) → tuple[Set[int], Set[int], int]

Return a row basis, a column basis, and rank, of mat, whilst ignoring ignored_rows and ignored_cols.

Added in version 3.0.0.

Adjacencies

cdd.matrix_adjacency(mat: Matrix) → Sequence[Set[int]]

Generate the input adjacency of the polyhedron represented by mat.

H-representation: For each face, list adjacent faces. V-representation: For each vertex, list adjacent vertices.

Note

The implementation uses linear programming, instead of the double description method, so this function should work for large scale problems.

See also

The copy_input_adjacency() function performs a similar operation, using the double description method.

Warning

This function assumes that the matrix has no redundancies. Call matrix_canonicalize() first if need be.

Added in version 3.0.0.

cdd.matrix_weak_adjacency(mat: Matrix) → Sequence[Set[int]]

Generate the weak input adjacency of the polyhedron represented by mat.

H-representation: For each face, list adjacent faces. V-representation: For each vertex, list adjacent vertices.

Note

The implementation uses linear programming, instead of the double description method, so this function should work for large scale problems.

See also

The copy_input_adjacency() function performs a similar operation, using the double description method.

Warning

This function assumes that the matrix has no redundancies. Call matrix_canonicalize() first if need be.

Added in version 3.0.0.

Canonicalization

cdd.matrix_canonicalize(mat: Matrix) → tuple[Set[int], Set[int], Sequence[int | None]]

Transform to canonical representation by recognizing all implicit linearities and all redundancies. These are returned as a pair of sets of row indices, along with a sequence of new row positions (None for removed rows).

This function has the same effect as calling matrix_canonicalize_linearity() followed by matrix_redundancy_remove().

Added in version 1.0.3.

Changed in version 3.0.0: Also return new row positions.

cdd.matrix_canonicalize_linearity(mat: Matrix) → tuple[Set[int], Sequence[int | None]]

Add all implicit linearities to the lin_set, and then remove all redundant linearities (e.g. everything in lin_set), by finding a basis for the linearity rows.

Returns implicit linearities as a sets of row indices, along with a sequence of new row positions (None for removed rows).

Added in version 3.0.0.

cdd.matrix_redundancy_remove(mat: Matrix) → tuple[Set[int], Sequence[int | None]]

Remove all redundant non-linearity rows (e.g. everything outside of lin_set).

Returns redundant rows as a set of row indices, along with a sequence of new row positions (None for removed rows).

Added in version 3.0.0.

Redundancy Checks

cdd.redundant(mat: Matrix, row: int) → Sequence[float] | None

A certificate in case row is not redundant for mat, otherwise None.

A row is redundant in the H- or V-representation if its removal does not affect the polyhedron.

For the H-representation, the “no redundancy” certificate \(x\) is a solution that satisfies all constraints but violates row, i.e.

\[\begin{split}0&> b_j+A_j x \\ 0&\le b_i+A_i x \qquad\forall i\notin L,\,i\neq j \\ 0&= b_i+A_i x \qquad\forall i\in L,\,i\neq j\end{split}\]

For the V-representation, the “no redundancy” certificate \((z_0,z)\) is a halfspace \(H_{z_0,z}^{\ge}\) that contains all generators but does not contain row, i.e.

\[\begin{split}0&> b_j z_0 + A_j z \\ 0&\le b_i z_0 + A_i z \qquad\forall i\notin L,\,i\neq j \\ 0&= b_i z_0 + A_i z \qquad\forall i\in L,\,i\neq j\end{split}\]

Warning

Linearity rows are not checked i.e. row should not be in the lin_set.

Added in version 3.0.0.

cdd.s_redundant(mat: Matrix, row: int) → Sequence[float] | None

A certificate in case row is not strongly redundant for mat, otherwise None.

A row is strongly redundant in the H-representation if every point in the polyhedron satisfies it with strict inequality. A row is strongly redundant in the V-representation if it is in the relative interior of the polyhedron.

For the H-representation, the “no strong redundancy” certificate \(x\) is a feasible solution satisfying the constraint row with equality, i.e.

\[\begin{split}0&= b_j+A_j x \\ 0&\le b_i+A_i x \qquad\forall i\notin L,\,i\neq j \\ 0&= b_i+A_i x \qquad\forall i\in L,\,i\neq j\end{split}\]

For the V-representation, the “no strong redundancy” certificate \((z_0,z)\) is a feasible halfspace \(H_{z_0,z}^{\ge}\) that contains the generator row on its edge, i.e.

\[\begin{split}0&= b_j z_0 + A_j z \\ 0&\le b_i z_0 + A_i z \qquad\forall i\notin L,\,i\neq j \\ 0&= b_i z_0 + A_i z \qquad\forall i\in L,\,i\neq j\end{split}\]

Warning

Linearity rows are not checked i.e. row should not be in the lin_set.

Added in version 3.0.0.

cdd.implicit_linearity(mat: Matrix, row: int) → Sequence[float] | None

A certificate in case row is not implicitly linear for mat, otherwise None.

A row is implicitly linear in the H- or V-representation if adding it to the linearity set lin_set does not affect the polyhedron.

For the H-representation, the “no implicit linearity” certificate \(x\) is a feasible solution satisfying inequality row with strict inequality, i.e.

\[\begin{split}0&< b_j+A_j x \\ 0&\le b_i+A_i x \qquad\forall i\notin L,\,i\neq j \\ 0&= b_i+A_i x \qquad\forall i\in L,\,i\neq j\end{split}\]

For the V-representation, the “no implicit linearity” certificate \((z_0,z)\) is a feasible halfspace \(H_{z_0,z}^{\ge}\) that strictly contains the generator row, i.e.

\[\begin{split}0&< b_j z_0 + A_j z \\ 0&\le b_i z_0 + A_i z \qquad\forall i\notin L,\,i\neq j \\ 0&= b_i z_0 + A_i z \qquad\forall i\in L,\,i\neq j\end{split}\]

Warning

Linearity rows are not checked i.e. row should not be in the lin_set.

Added in version 3.0.0.

cdd.redundant_rows(mat: Matrix) → Set[int]

Returns all non-linearity rows that are redundant for mat.

Added in version 3.0.0.

cdd.s_redundant_rows(mat: Matrix) → Set[int]

Returns all non-linearity rows that are strongly redundant for mat.

Added in version 3.0.0.

cdd.implicit_linearity_rows(mat: Matrix) → Set[int]

Returns all non-linearity rows that are implicitly linear for mat.

Added in version 3.0.0.

Linear Programming

cdd.linprog_solve(lp: LinProg, solver: LPSolverType = LPSolverType.DUAL_SIMPLEX) → None

Solve the linear program lp using solver.

Polyhedron Operations

cdd.copy_input(poly: Polyhedron) → Matrix

Returns the original matrix that the polyhedron was constructed from.

Added in version 3.0.0.

cdd.copy_output(poly: Polyhedron) → Matrix

Returns the dual representation of the original matrix. If the original was a H-representation, this will return its V-representation, and vice versa.

Note

The output is not guaranteed to be minimal, that is, it can still contain redundancy. Use matrix_canonicalize() on the output to remove redundancies.

Added in version 3.0.0.

cdd.copy_inequalities(poly: Polyhedron) → Matrix

Copy a H-representation of the inequalities.

cdd.copy_generators(poly: Polyhedron) → Matrix

Copy a V-representation of all the generators.

cdd.copy_adjacency(poly: Polyhedron) → Sequence[Set[int]]

Get the adjacencies.

H-representation: For each vertex, list adjacent vertices. V-representation: For each face, list adjacent faces.

Added in version 2.1.1.

cdd.copy_incidence(poly: Polyhedron) → Sequence[Set[int]]

Get the incidences.

H-representation: For each vertex, list adjacent faces. V-representation: For each face, list adjacent vertices.

Added in version 2.1.1.

cdd.copy_input_adjacency(poly: Polyhedron) → Sequence[Set[int]]

Get the input adjacencies.

H-representation: For each face, list adjacent faces. V-representation: For each vertex, list adjacent vertices.

See also

The matrix_adjacency() and matrix_weak_adjacency() functions perform a similar operation, using linear programming.

Added in version 2.1.1.

cdd.copy_input_incidence(poly: Polyhedron) → Sequence[Set[int]]

Get the input incidences.

H-representation: For each face, list adjacent vertices. V-representation: For each vertex, list adjacent faces.

Added in version 2.1.1.

Elimination

cdd.fourier_elimination(mat: Matrix) → Matrix

Eliminate the last variable from the system of linear inequalities mat.

Warning

This implementation can only handle inequality constraints. If your system has equality constraints, either convert them into pairs of inequalities first, or use block_elimination() instead.

Note

The output is not guaranteed to be minimal, that is, it can still contain redundancy. Use matrix_canonicalize() on the output to remove redundancies.

Added in version 3.0.0.

cdd.block_elimination(mat: Matrix, col_set: Container[int]) → Matrix

Eliminate the variables col_set from the system of linear inequalities mat. It does this by using the generators of the dual linear system, where the generators are calculated using the double description algorithm.

Note

The output is not guaranteed to be minimal, that is, it can still contain redundancy. Use matrix_canonicalize() on the output to remove redundancies.

Added in version 3.0.0.