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()). 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.

Polyhedra.BlockElimination — Type.

BlockElimination

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

Polyhedra.ProjectGenerators — Type.

ProjectGenerators

Computation of the projection by computing the V-representation and projecting them.

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.

Polyhedra.project — Function.

project(p::Polyhedron, pset, algo)

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

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[1], v[1]))

but it is much more efficient. The code above does a polyhedral projection while this function simply replace 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).