Representation

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.fulldim — Function.
fulldim(rep::Rep)

Returns the dimension of the space in which the representation is defined. That is, a straight line in a 3D space has fulldim 3.

source
MultivariatePolynomials.coefficienttype — Function.
coefficienttype(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{N, T, AT} <: HRepElement{N, T}
    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{align*} x_1 + x_2 &\leq 1 \\ x_1 - x_2 &\leq 0 \\ x_1 & \geq 0. \end{align*}\]

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{align*} x_1 + x_2 &= 1 \\ x_1 &\geq 0 \\ x_2 &\geq 0 \end{align*}\]

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{N, T, AT} <: HRepElement{N, T}
    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

Polyhedra.hrep — Function.
hrep(p::Polyhedron)

Returns an H-representation for the polyhedron p.

source
hrep(hyperplanes::HyperPlaneIt)

Creates an affine space 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)

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

Examples

For instance, the simplex

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

can be created as follows:

hrep([HalfSpace([-1, 0], 0)], [HyperPlane([1, 1], 1), HalfSpace([0, -1], 0)])
source
hrep(halfspaces::HalfSpaceIt)

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

Examples

For instance, the polytope

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

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::IntSet=IntSet())

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

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 and rays

Polyhedra.AbstractPoint — Constant.
const AbstractPoint{N, T} = Union{Point{N, T}, AbstractVector{T}}

A point in dimension N and of coefficient type T.

source
Polyhedra.Ray — Type.
struct Ray{N, T, AT <: MyVec{N, 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{N, T, AT <: MyVec{N, 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

Polyhedra.vrep — Function.
vrep(p::Polyhedron)

Returns a V-representation for the polyhedron p.

source
vrep(lines::LineIt)

Creates an affine space 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)

Creates a V-representation for the polytope 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)

Creates a V-representation for the polyhedral cone 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 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)

Creates a V-representation for the polyhedron 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::IntSet=IntSet())

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

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