Representation

Polyhedra can be described in 2 different ways.

  1. H-representation: As the intersection of finitely many halfspaces given by its facets.
  2. V-representation: As the convex hull of its vertices + the conic hull of its rays where '+' is the Minkowski sum.

In Polyhedra.jl, those representations are given the respective abstract types HRepresentation and VRepresentation which are themself subtypes of Representation.

These functions can be called on both H-representation and V-representation

Polyhedra.fulldimFunction
fulldim(rep::Rep)::Int

Returns the dimension of the space in which polyhedron, representation, element or vector is defined. That is, a straight line in a 3D space has fulldim 3 even if its dimension is 1.

source
Polyhedra.FullDimType
FullDim(p)::FullDim

Similar to fulldim but used for type stability with the vector type. If the vector type is StaticArrays.SVector then it returns a StaticArrays.Size.

source

H-representation

The fundamental element of an H-representation is the halfspace

Polyhedra.HalfSpaceType
struct HalfSpace{T, AT} <: HRepElement{T, AT}
    a::AT
    β::T
end

An halfspace defined by the set of points $x$ such that $\langle a, x \rangle \le \beta$.

source

An H-representation can be created as the intersection of several halfspaces. For instance, the polytope

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

can be created as follows:

HalfSpace([1, 1], 1) ∩ HalfSpace([1, -1], 0) ∩ HalfSpace([-1, 0], 0)

Even if HalfSpaces are enough to describe any polyhedron, it is sometimes important to represent the fact that the polyhedron is contained in an affine subspace. For instance, the simplex

\[\begin{aligned} x_1 + x_2 &= 1 \\ x_1 &\geq 0 \\ x_2 &\geq 0 \end{aligned}\]

is 1-dimensional even if it is defined in a 2-dimensional space.

The fundamental element of an affine subspace is the hyperplane

Polyhedra.HyperPlaneType
struct HyperPlane{T, AT} <: HRepElement{T, AT}
    a::AT
    β::T
end

An hyperplane defined by the set of points $x$ such that $\langle a, x \rangle = \beta$.

source

An affine subspace can be created as the intersection of several hyperplanes. For instance

HyperPlane([1, 1], 1) ∩ HyperPlane([1, 0], 0)

represents the 0-dimensional affine subspace only containing the point $(0, 1)$.

To represent a polyhedron that is not full-dimensional, hyperplanes and halfspaces can be mixed in any order. For instance, the simplex defined above can be obtained as follows:

HalfSpace([-1, 0], 0) ∩ HyperPlane([1, 1], 1) ∩ HalfSpace([0, -1], 0)

In addition to being created incrementally with intersections, an H-representation can also be created using the hrep function. The hrep function is also used to query the H-representation of a given polyhedron.

Polyhedra.hrepFunction
hrep(p::Polyhedron)

Returns an H-representation for the polyhedron p.

source
hrep(hyperplanes::HyperPlaneIt; d::FullDim)

Creates an affine space of full dimension d from the list of hyperplanes hyperplanes.

Examples

hrep([HyperPlane([0, 1, 0], 1), HyperPlane([0, 0, 1], 0)])

creates the 1-dimensional affine subspace containing all the points $(x_1, 0, 0)$, i.e. the $x_1$-axis.

hrep([HyperPlane([1, 1], 1), HyperPlane([1, 0], 0)])

creates the 0-dimensional affine subspace only containing the point $(0, 1)$.

source
hrep(hyperplanes::HyperPlaneIt, halfspaces::HalfSpaceIt; d::FullDim)

Creates an H-representation for the polyhedron of full dimension d equal to the intersection of the hyperplanes hyperplanes and halfspaces halfspaces.

Examples

For instance, the simplex

\[\begin{aligned} x_1 + x_2 &= 1 \\ x_1 &\geq 0 \\ x_2 &\geq 0 \end{aligned}\]

can be created as follows:

julia> hrep([HyperPlane([1, 1], 1)], [HalfSpace([0, -1], 0), HalfSpace([-1, 0], 0)])
H-representation Polyhedra.Intersection{Int64, Vector{Int64}, Int64}:
1-element iterator of HyperPlane{Int64, Vector{Int64}}:
 HyperPlane([1, 1], 1),
2-element iterator of HalfSpace{Int64, Vector{Int64}}:
 HalfSpace([0, -1], 0)
 HalfSpace([-1, 0], 0)
source
hrep(halfspaces::HalfSpaceIt; d::FullDim)

Creates an H-representation for the polyhedron of full dimension d equal to the intersection of the halfspaces halfspaces.

Examples

For instance, the polytope

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

can be created as follows:

hrep([HalfSpace([1, 1], 1), HalfSpace([1, -1], 0), HalfSpace([-1, 0], 0)])
source
hrep(model::JuMP.Model)

Builds an H-representation from the feasibility set of the JuMP model model. Note that if non-linear constraint are present in the model, they are ignored.

source
hrep(A::AbstractMatrix, b::AbstractVector, linset::BitSet=BitSet())

Creates an H-representation for the polyhedron defined by the inequalities $\langle A_i, x \rangle = b_i$ if i in linset and $\langle A_i, x \rangle \le b_i$ otherwise where $A_i$ is the $i$th row of A, i.e. A[i,:] and $b_i$ is b[i].

source

The H-representation of a given polyhedron can be altered with the Polyhedra.resethrep! and Polyhedra.sethrep!. Use Polyhedra.sethrep! with caution as it does not invalidate the V-representation! Use Polyhedra.resethrep! in case you are unsure on which one to use.

Polyhedra.resethrep!Function
Polyhedra.resethrep!(p::Polyhedron, h::HRepresentation, redundancy::Redundancy = UNKNOWN_REDUNDANCY)

Reset the H-representation of p to h. The redundancy of p is assumed to be redundancy; see Polyhedra.Redundancy.

Info

The representation is not assumed to be a valid representation for p so it invalidates the V-representation of p. Use Polyhedra.sethrep! if h is known to be a valid representation for p.

source
Polyhedra.sethrep!Function
Polyhedra.sethrep!(p::Polyhedron, h::HRepresentation, redundancy::Redundancy = UNKNOWN_REDUNDANCY)

Reset the H-representation of p to h. The redundancy of p is assumed to be redundancy; see Polyhedra.Redundancy.

Warning

The representation is assumed to be a valid representation for p so it does not invalidate the V-representation of p if it was already computed previously. Use Polyhedra.resethrep! if h is not known to be a valid representation for p.

source

Interface

An H-representation is represented as an intersection halfspaces and hyperplanes. The halfspaces can be obtained with halfspaces and the hyperplanes with hyperplanes. As an hyperplane $\langle a, x \rangle = \beta$ is the intersection of the two halfspaces $\langle a, x \rangle \le \beta$ and $\langle a, x \rangle \ge \beta$, even if the H-representation contains hyperplanes, a list of halfspaces whose intersection is the polyhedron can be obtained with allhalfspaces, which has nhalfspaces(p) + 2nhyperplanes(p) elements for an H-representation p since each hyperplane is split in two halfspaces.

Polyhedra.halfspacesFunction
halfspaces(hrep::HRep)

Returns an iterator over the halfspaces of the H-representation hrep.

source
Polyhedra.allhalfspacesFunction
allhalfspaces(hrep::HRep)

Returns an iterator over the halfspaces and hyperplanes in the H-representation hrep splitting hyperplanes in two halfspaces.

Examples

hrep = HyperPlane([1, 0], 1) ∩ HalfSpace([0, 1], 1)
collect(allhalfspaces(hrep)) # Returns [HalfSpace([1, 0]), HalfSpace([-1, 0]), HalfSpace([0, 1])]
source
Polyhedra.nallhalfspacesFunction
nallhalfspaces(hrep::HRep)

Returns the number of halfspaces plus twice the number of hyperplanes in the H-representation hrep, i.e. length(allhalfspaces(hrep))

source

V-representation

The fundamental elements of an V-representation are the points (represented by AbstractVectors and and rays

Polyhedra.RayType
struct Ray{T, AT <: AbstractVector{T}}
    a::AT
end

The conic hull of a, i.e. the set of points λa where λ is any nonnegative real number.

source

A V-representation can be created as the minkowski sum between a convex hull of points and a conic hull of rays. For instance, the positive orthant without the simplex defined in the H-representation section can be created as follows:

convexhull([1, 0], [0, 1]) + conichull([1, 0], [0, 1])

The V-representation represents the polyhedron as a minkowski sum of a polytope and a polyhedral cone. The polytope is represented using a P-representation : a convex hull of points. The polyhedral cone is represented using an R-representation : a conic hull of rays.

Even if rays are enough to describe any polyhedral cone, it is sometimes important to represent the fact that the polyhedron contains an affine subspace. For instance, the polyhedron created with

convexhull([1, 0], [0, 1]) + conichull([1, 1], [-1, -1])

contains the line [1, 1].

The fundamental element of an affine subspace is the line

Polyhedra.LineType
struct Line{T, AT <: AbstractVector{T}}
    a::AT
end

The conic hull of a and -a, i.e. the set of points λa where λ is any real number.

source

An affine subspace can be created as the conic hull/minkownski sum of several lines. For instance

conichull(Line([1, 0]), Line([0, 1]))

represents the full space.

In addition to being created incrementally with convex hull and minkowsky addition, a V-representation can also be created using the vrep function. The vrep function is also used to query the V-representation of a given polyhedron.

Polyhedra.vrepFunction
vrep(p::Polyhedron)

Returns a V-representation for the polyhedron p.

source
vrep(lines::LineIt; d::FullDim)

Creates an affine space of full dimension d from the list of lines lines.

Examples

vrep([Line([1, 0, 0]), Line([0, 1, 0])])

creates the 2-dimensional affine subspace containing all the points $(x_1, x_2, 0)$, i.e. the $x_1$$x_2$-plane.

source
vrep(points::PointIt; d::FullDim)

Creates a V-representation for the polytope of full dimension d equal to the convex hull of the points points.

Examples

The convex hull of $(0, 0)$, $(0, 1)$ and $(1/2, 1/2)$ can be created as follows using exact arithmetic

vrep([[0, 0], [0, 1], [1//2, 1//2]])

or as follows using floating point arithmetic

vrep([[0, 0], [0, 1], [1/2, 1/2]])
source
vrep(lines::LineIt, rays::RayIt; d::FullDim)

Creates a V-representation for the polyhedral cone of full dimension d equal to the conic hull of the lines lines and rays rays.

Examples

vrep([Line([0, 1])], [Ray([1, 0])])

creates a V-representation for the halfspace $x_1 \ge 0$.

source
vrep(rays::RayIt)

Creates a V-representation for the polyhedral cone of full dimension d equal to the conic hull of the rays rays.

Examples

vrep([Ray([1, 0]), Ray([0, 1])])

creates a V-representation for positive orthant.

source
vrep(points::PointIt, lines::LineIt, rays::RayIt;
     d = Polyhedra.FullDim_rec(points, lines, rays))

Creates a V-representation for the polyhedron of full dimension d equal to the minkowski sum of the convex hull of points with the conic hull of lines and rays.

source
vrep(V::AbstractMatrix, R::AbstractMatrix, Rlinset::BitSet=BitSet())

Creates a V-representation for the polyhedron defined by the points $V_i$, lines $R_i$ if i in Rlinset and rays $R_i$ otherwise where $V_i$ (resp. $R_i$) is the $i$th row of V (resp. R), i.e. V[i,:] (resp. R[i,:]).

source

The H-representation of a given polyhedron can be altered with the Polyhedra.resetvrep! and Polyhedra.setvrep!. Use Polyhedra.setvrep! with caution as it does not invalidate the V-representation! Use Polyhedra.resetvrep! in case you are unsure on which one to use.

Polyhedra.resetvrep!Function
Polyhedra.resetvrep!(p::Polyhedron, v::VRepresentation, redundancy::Redundancy = UNKNOWN_REDUNDANCY)

Reset the V-representation of p to v. The redundancy of p is assumed to be redundancy; see Polyhedra.Redundancy.

Info

The representation is not assumed to be a valid representation for p so it invalidates the H-representation of p. Use Polyhedra.setvrep! if v is known to be a valid representation for p.

source
Polyhedra.setvrep!Function
Polyhedra.setvrep!(p::Polyhedron, v::HRepresentation, redundancy::Redundancy = UNKNOWN_REDUNDANCY)

Reset the H-representation of p to v. The redundancy of p is assumed to be redundancy; see Polyhedra.Redundancy.

Warning

The representation is assumed to be a valid representation for p so it does not invalidate the H-representation of p if it was already computed previously. Use Polyhedra.resetvrep! if v is not known to be a valid representation for p.

source

Interface

A P-representation is represented as a convex hull points. The points can be obtained with points.

Polyhedra.pointsFunction
points(vrep::VRep)

Returns an iterator over the points of the V-representation vrep.

source

An R-representation is represented as a conic hull of lines and rays. The rays can be obtained with rays and the lines with lines. As a line $r$ is the conic hull of of the two rays $r$ and $-r$, even if the R-representation contains lines, a list of rays whose conic hull is the polyhedral cone can be obtained with allrays, which has nrays(R) + 2nlines(R) elements for an R-representation R since each line is split in two rays.

Polyhedra.raysFunction
rays(vrep::VRep)

Returns an iterator over the rays of the V-representation vrep.

source
Polyhedra.nraysFunction
nrays(vrep::VRep)

Returns the number of rays of the V-representation vrep.

source
Polyhedra.linesFunction
lines(vrep::VRep)

Returns an iterator over the lines of the V-representation vrep.

source
Polyhedra.nlinesFunction
nlines(vrep::VRep)

Returns the number of lines of the V-representation vrep.

source
Polyhedra.allraysFunction
allrays(vrep::VRep)

Returns an iterator over the rays and lines in the V-representation vrep splitting lines in two rays.

Examples

vrep = Line([1, 0]) + Ray([0, 1])
collect(allrays(vrep)) # Returns [Ray([1, 0]), Ray([-1, 0]), Ray([0, 1])]
source
Polyhedra.nallraysFunction
nallrays(vrep::VRep)

Returns the number of rays plus twice the number of lines in the V-representation vrep, i.e. length(allrays(vrep))

source