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

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