Polyhedron in constraint representation (HPolyhedron)

HPolyhedron{N, VN<:AbstractVector{N}} <: AbstractPolyhedron{N}

Type that represents a convex polyhedron in constraint representation, that is, a finite intersection of half-spaces,

\[P = \bigcap_{i = 1}^m H_i,\]

where each $H_i = \{x \in \mathbb{R}^n : a_i^T x \leq b_i \}$ is a half-space, $a_i \in \mathbb{R}^n$ is the normal vector of the $i$-th half-space and $b_i$ is the displacement. The set $P$ may or may not be bounded (see also HPolytope, which assumes boundedness).

Fields

• constraints – vector of linear constraints

dim(P::HPoly)

Return the dimension of a polyhedron in constraint representation.

Input

• P – polyhedron in constraint representation

Output

The ambient dimension of the polyhedron in constraint representation. If it has no constraints, the result is $-1$.

ρ(d::AbstractVector{M}, P::HPoly{N};
  solver=default_lp_solver(M, N)) where {M, N}

Evaluate the support function of a polyhedron in constraint representation in a given direction.

Input

• d – direction
• P – polyhedron in constraint representation
• solver – (optional, default: default_lp_solver(M, N)) the backend used to solve the linear program

Output

The evaluation of the support function for the polyhedron. If a polytope is unbounded in the given direction, we throw an error. If a polyhedron is unbounded in the given direction, the result is Inf.

σ(d::AbstractVector{M}, P::HPoly{N};
  solver=default_lp_solver(M, N) where {M, N}

Return a support vector of a polyhedron in constraint representation in a given direction.

Input

• d – direction
• P – polyhedron in constraint representation
• solver – (optional, default: default_lp_solver(M, N)) the backend used to solve the linear program

Output

The support vector in the given direction. If a polytope is unbounded in the given direction, we throw an error. If a polyhedron is unbounded in the given direction, the result contains ±Inf entries.

addconstraint!(P::HPoly, constraint::HalfSpace)

Add a linear constraint to a polyhedron in constraint representation.

Input

• P – polyhedron in constraint representation
• constraint – linear constraint to add

Notes

It is left to the user to guarantee that the dimension of all linear constraints is the same.

constraints_list(P::HPoly)

Return the list of constraints defining a polyhedron in constraint representation.

Input

• P – polyhedron in constraint representation

Output

The list of constraints of the polyhedron.

tohrep(P::HPoly)

Return a constraint representation of the given polyhedron in constraint representation (no-op).

Input

• P – polyhedron in constraint representation

Output

The same polyhedron instance.

tovrep(P::HPoly; [backend]=default_polyhedra_backend(P))

Transform a polytope in constraint representation to a polytope in vertex representation.

Input

• P – polytope in constraint representation
• backend – (optional, default: default_polyhedra_backend(P)) the backend for polyhedral computations

Output

A VPolytope which is a vertex representation of the given polytope in constraint representation.

Notes

The conversion may not preserve the numeric type (e.g., with N == Float32) depending on the backend. For further information on the supported backends see Polyhedra's documentation.

normalize(P::HPoly{N}, p::Real=N(2)) where {N}

Normalize a polyhedron in constraint representation.

Input

• P – polyhedron in constraint representation
• p – (optional, default: 2) norm

Output

A new polyhedron in constraint representation whose normal directions $a_i$ are normalized, i.e., such that $‖a_i‖_p = 1$ holds.

translate(P::HPoly, v::AbstractVector; [share]::Bool=false)

Translate (i.e., shift) a polyhedron in constraint representation by a given vector.

Input

• P – polyhedron in constraint representation
• v – translation vector
• share – (optional, default: false) flag for sharing unmodified parts of the original set representation

Output

A translated polyhedron in constraint representation.

Notes

The normal vectors of the constraints (vector a in a⋅x ≤ b) are shared with the original constraints if share == true.

Algorithm

We translate every constraint.

remove_redundant_constraints(P::HPoly{N}; [backend]=nothing) where {N}

Remove the redundant constraints in a polyhedron in constraint representation.

Input

• P – polyhedron
• backend – (optional, default: nothing) the backend used to solve the linear program

Output

A polyhedron equivalent to P but with no redundant constraints, or an empty set if P is detected to be empty, which may happen if the constraints are infeasible.

Notes

If backend is nothing, it defaults to default_lp_solver(N).

Algorithm

See remove_redundant_constraints!(::AbstractVector{<:HalfSpace}) for details.

remove_redundant_constraints!(P::HPoly{N}; [backend]=nothing) where {N}

Remove the redundant constraints of a polyhedron in constraint representation; the polyhedron is updated in-place.

Input

• P – polyhedron
• backend – (optional, default: nothing) the backend used to solve the linear program

Output

true if the method was successful and the polyhedron P is modified by removing its redundant constraints, and false if P is detected to be empty, which may happen if the constraints are infeasible.

Notes

If backend is nothing, it defaults to default_lp_solver(N).

Algorithm

See remove_redundant_constraints!(::AbstractVector{<:HalfSpace}) for details.

rand(::Type{HPolyhedron}; [N]::Type{<:Real}=Float64, [dim]::Int=2,
     [rng]::AbstractRNG=GLOBAL_RNG, [seed]::Union{Int, Nothing}=nothing)

Create a random polyhedron.

Input

• HPolyhedron – type for dispatch
• N – (optional, default: Float64) numeric type
• dim – (optional, default: 2) dimension (is ignored)
• rng – (optional, default: GLOBAL_RNG) random number generator
• seed – (optional, default: nothing) seed for reseeding

Output

A random polyhedron.

Algorithm

We first create a random polytope and then for each constraint randomly (50%) decide whether to include it.