Polyhedron in constraint representation (HPolyhedron)

HPolyhedron{N<:Real} <: AbstractPolyhedron{N}

Type that represents a convex polyhedron in H-representation.

Fields

• constraints – vector of linear constraints

dim(P::HPoly{N}) where {N<:Real}

Return the dimension of a polyhedron in H-representation.

Input

• P – polyhedron in H-representation

Output

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

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

Evaluate the support function of a polyhedron (in H-representation) in a given direction.

Input

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

Output

The support function of 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{N}, P::HPoly{N}; solver=default_lp_solver(N)
 ) where {N<:Real}

Return the support vector of a polyhedron (in H-representation) in a given direction.

Input

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

Output

The support vector in the given direction.

addconstraint!(P::HPoly{N}, constraint::LinearConstraint{N}) where {N<:Real}

Add a linear constraint to a polyhedron in H-representation.

Input

• P – polyhedron in H-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{N}) where {N<:Real}

Return the list of constraints defining a polyhedron in H-representation.

Input

• P – polyhedron in H-representation

Output

The list of constraints of the polyhedron.

tohrep(P::HPoly{N}) where {N<:Real}

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{N};
      [backend]=default_polyhedra_backend(P, N)) where {N<:Real}

Transform a polyhedron in H-representation to a polytope in V-representation.

Input

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

Output

The VPolytope which is the vertex representation of the given polyhedron 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.

isempty(P::HPoly{N}, witness::Bool=false; [usepolyhedrainterface]::Bool=false, [solver]=defaultlpsolver(N), [backend]=nothing) where {N<:Real}

Determine whether a polyhedron is empty.

Input

• P – polyhedron
• witness – (optional, default: false) compute a witness if activated
• use_polyhedra_interface – (optional, default: false) if true, we use the Polyhedra interface for the emptiness test
• solver – (optional, default: default_lp_solver(N)) LP-solver backend
• backend – (optional, default: nothing) backend for polyhedral computations in Polyhedra; its value is set internally (see the Notes below for details)

Output

• If witness option is deactivated: true iff $P = ∅$
• If witness option is activated:
  • (true, []) iff $P = ∅$
  • (false, v) iff $P ≠ ∅$ and $v ∈ P$

Notes

The default value of the backend is set internally and depends on whether the use_polyhedra_interface option is set or not. If the option is set, we use default_polyhedra_backend(P, N).

Witness production is not supported if use_polyhedra_interface is true.

Algorithm

The algorithm sets up a feasibility LP for the constraints of P. If use_polyhedra_interface is true, we call Polyhedra.isempty. Otherwise, we set up the LP internally.

translate(P::HPoly{N}, v::AbstractVector{N}; share::Bool=false
         ) where {N<:Real}

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.

polyhedron(P::HPoly{N};
           [backend]=default_polyhedra_backend(P, N)) where {N<:Real}

Return an HRep polyhedron from Polyhedra.jl given a polytope in H-representation.

Input

• P – polytope
• backend – (optional, default: call default_polyhedra_backend(P, N)) the polyhedral computations backend

Output

An HRep polyhedron.

Notes

For further information on the supported backends see Polyhedra's documentation.

remove_redundant_constraints(P::HPoly{N};
                             backend=default_lp_solver(N)
                            ) where {N<:Real}

Remove the redundant constraints in a polyhedron in H-representation.

Input

• P – polyhedron
• backend – (optional, default: default_lp_solver(N)) 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.

Algorithm

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

remove_redundant_constraints!(P::HPoly{N};
                              backend=default_lp_solver(N)) where {N<:Real}

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

Input

• P – polyhedron
• backend – (optional, default: default_lp_solver(N)) 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.

Algorithm

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

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

Create a 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 polyhedron.

Algorithm

We first create a random polytope and then randomly remove some of the constraints.

isbounded(P::HPolyhedron)

Determine whether a polyhedron in constraint representation is bounded.

Input

• P – polyhedron in constraint representation

Output

true iff the polyhedron is bounded.

Algorithm

We first check if the polyhedron has more than max(dim(P), 1) constraints, which is a necessary condition for boundedness. If so, we check boundedness via isbounded_unit_dimensions.

vertices_list(P::HPolyhedron{N}) where {N<:Real}

Return the list of vertices of a polyhedron in constraint representation.

Input

• P – polyhedron in constraint representation

Output

This function returns an error because the polyhedron is possibly unbounded. If P is known to be bounded, try converting to HPolytope first:

julia> P = HPolyhedron([HalfSpace([1.0, 0.0], 1.0),
                        HalfSpace([0.0, 1.0], 1.0),
                        HalfSpace([-1.0, 0.0], 1.0),
                        HalfSpace([0.0, -1.0], 1.0)]);

julia> P_as_polytope = convert(HPolytope, P);

singleton_list(P::HPolyhedron{N}) where {N<:Real}

Return the vertices of a polyhedron in H-representation as a list of singletons.

Input

• P – polytope in constraint representation

Output

This function returns an error because the polyhedron is possibly unbounded. If P is known to be bounded, try converting to HPolytope first.