Representation

Polyhedra can be described in 2 different ways.

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

Polyhedra.HRepresentation — Type

HRepresentation{T<:Real}

Supertype for H-representations with coefficient type T.

source

Polyhedra.VRepresentation — Type

VRepresentation{T<:Real}

Supertype for V-representations coefficient type T.

source

Polyhedra.Representation — Type

Representation{T<:Real}

Supertype for H-(or V-)representations with coefficient type T.

source

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.fulldim — Function

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.FullDim — Type

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

Polyhedra.coefficient_type — Function

coefficient_type(rep::Rep)

Returns the type of the coefficients used in the representation of rep.

source

H-representation

The fundamental element of an H-representation is the halfspace

Polyhedra.HalfSpace — Type

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.HyperPlane — Type

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.hrep — Function

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.halfspaces — Function

halfspaces(hrep::HRep)

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

source

Polyhedra.nhalfspaces — Function

nhalfspaces(hrep::HRep)

Returns the number of halfspaces of the H-representation hrep.

source

Polyhedra.hashalfspaces — Function

hashalfspaces(hrep::HRep)

Returns whether the H-representation hrep has any halfspace.

source

Polyhedra.hyperplanes — Function

hyperplanes(hrep::HRep)

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

source

Polyhedra.nhyperplanes — Function

nhyperplanes(hrep::HRep)

Returns the number of hyperplanes of the H-representation hrep.

source

Polyhedra.hashyperplanes — Function

hashyperplanes(hrep::HRep)

Returns whether the H-representation hrep has any hyperplane.

source

Polyhedra.allhalfspaces — Function

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.nallhalfspaces — Function

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

Polyhedra.hasallhalfspaces — Function

hasallhalfspaces(hrep::HRep)

Returns whether the H-representation hrep contains any halfspace or hyperplane.

source

V-representation

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

Polyhedra.Ray — Type

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.Line — Type

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.vrep — Function

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.points — Function

points(vrep::VRep)

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

source

Polyhedra.npoints — Function

npoints(vrep::VRep)

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

source

Polyhedra.haspoints — Function

haspoints(vrep::VRep)

Returns whether the V-representation vrep has any point.

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.rays — Function

rays(vrep::VRep)

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

source

Polyhedra.nrays — Function

nrays(vrep::VRep)

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

source

Polyhedra.hasrays — Function

hasrays(vrep::VRep)

Returns whether the V-representation vrep has any ray.

source

Polyhedra.lines — Function

lines(vrep::VRep)

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

source

Polyhedra.nlines — Function

nlines(vrep::VRep)

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

source

Polyhedra.haslines — Function

haslines(vrep::VRep)

Returns whether the V-representation vrep has any line.

source

Polyhedra.allrays — Function

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.nallrays — Function

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

Polyhedra.hasallrays — Function

hasallrays(vrep::VRep)

Returns whether the V-representation vrep contains any ray or line.

source