GitHub

Projection/Elimination

Consider the polyhedron created in the beginning of this section. As a reminder, it represents the following H-representation:

\[\begin{align*} x_1 + x_2 &\leq 1 \\ x_1 - x_2 &\leq 0 \\ x_1 & \geq 0. \end{align*}\]

One can verify that for any $0 \leq x_2 \leq 1$, there exists a value $x_1$ such that $(x_1, x_2)$ is in this polyhedron. This means that the H-representation obtained by eliminating $x_1$ is:

\[\begin{align*} x_1 & \leq 1 \\ x_1 & \geq 0. \end{align*}\]

where $x_1$ in the H-representation above represents $x_2$ in the previous one. This can be obtained as follows

julia> poly_x2 = eliminate(poly, [1])
julia> hrep(poly_x2)
H-representation
begin
 2 2 rational
 1//1 -1//1
 0//1 1//1
end

There is two methods of computing the elimination implemented in CDDLib: Fourier-Motzkin elimination and block elimination. As written by K. Fukuda in CDD's documentation, "[Block elimination] might be a faster way to eliminate variables than the repeated [Fourier-Motzkin elimination] when the number of variables to eliminate is large". You can specify the method to use as a third argument, e.g. eliminate(poly, [1], FourierMotzkin()), eliminate(poly, [1], BlockElimination()). Block elimination is also implemented by Polyhedra for any library: it computes the extreme rays of a polyhedral cone with the library of the polyhedron. The resulting H-representation may however contain many redundant halfspaces so it is only used when explicitly requested, unless the library implements it natively. A third method can be chosen: ProjectGenerators. It computes the V-representation and then project each of its elements. This is the method of choice when the V-representation is already computed.

Polyhedra.FourierMotzkin — Type
FourierMotzkin

Computation of the projection by computing the H-representation and applying the Fourier-Motzkin elimination algorithm to it.

The resulting polyhedron may contain duplicates and/or redundancy. These can be removed with removehredundancy!.

source
Polyhedra.BlockElimination — Type
BlockElimination

Computation of the projection by computing the H-representation and applying the block elimination algorithm to it.

The idea is as follows. Consider a H-representation given by $Ax + By \le c$. For any $d$, the projection on the x variables belongs to the halfspace $d^\top x \le \delta$ where $\delta$ is

\[\begin{aligned} \max \; & d^\top x \\ \text{s.t.} & A x + By \le c \end{aligned}\]

By duality, this is equal to

\[\begin{aligned} \min \; & c^\top \nu \\ \text{s.t.} & A^\top \nu = d \\ & B^\top \nu = 0 \\ & \nu \ge 0 \end{aligned}\]

Let R be the matrix for which the columns are the extreme rays of the polyhedral cone defined by $B^\top \nu = 0, \nu \ge 0$. The program can be rewritten as

\[\begin{aligned} \min \; & c^\top \nu \\ \text{s.t.} & A^\top \nu = d \\ & \nu = R\lambda \\ & \lambda \ge 0 \end{aligned}\]

which is equivalent to

\[\begin{aligned} \min \; & c^\top R \lambda \\ \text{s.t.} & A^\top R \lambda = d \\ & \lambda \ge 0 \end{aligned}\]

Dualizing, we obtain

\[\begin{aligned} \max \; & d^\top x \\ \text{s.t.} & R^\top A x \le R^\top c \end{aligned}\]

where we see that $R^\top A x \le R^\top c$ is the H-representation of the projection. The hyperplanes $A x + B y = c$ are handled similarly, their multipliers $\nu$ are free so that the cone $B^\top \nu = 0$ may have lines. Each line $\ell$ of the cone gives the hyperplane $\ell^\top A x = \ell^\top c$ of the projection.

The extreme rays and lines of the cone are computed by the library of the polyhedron. The resulting polyhedron may contain redundancy. It can be removed with removehredundancy!.

source

If nothing is specified as in the block of code above, the behavior depends on the polyhedral library. If neither Fourier-Motzkin nor block elimination is implemented or if the V-representation is already computed then :ProjectGenerators is chosen. Otherwise, Polyhedra lets the library decide. In CDDLib, :FourierMotzkin is chosen when only the last dimension needs to be eliminated and :BlockElimination is chosen otherwise. Note that CDDLib only supports projecting the last trailing dimensions.

Polyhedra.eliminate — Function
eliminate(p::Polyhedron, delset, algo::EliminationAlgorithm)

Eliminate the dimensions in delset by projecting the polyhedron onto the remaining dimension.

source
Polyhedra.project — Function
project(p::Polyhedron, pset, algo)

Equivalent to eliminate(p, setdiff(1:fulldim(p), pset), algo).

source
Polyhedra.fixandeliminate — Function
fixandeliminate(p::HRep{T}, I, v)

Fix the variables with indices in I to the corresponding value in v. This is equivalent to doing the following:

function ei(i)
    a = zeros(T, fulldim(p))
    a[i] = one(T)
    a
end
eliminate(p ∩ HyperPlane(ei(I[1]), v[1]) ∩ ... ∩ HyperPlane(ei(I[n]), v[n]))

where n is the length of I (and v), but it is much more efficient. The code above does a polyhedral projection while this function simply replaces each halfspace ⟨a, x⟩ ≤ β (resp. each hyperplane ⟨a, x⟩ = β) by the halfspace ⟨a_J, x⟩ ≤ β - ⟨a_I, v⟩ (resp. the hyperplane ⟨a_J, x⟩ = β - ⟨a_I, v⟩) where J = setdiff(1:fulldim(p), I).

source