Capture the correspondence of vertices in VRep and inequalities in HRep

[shizejin]

Hi, I am trying to implement Vertex Enumeration algorithm for finding Nash equilibrium in QuantEcon/GameTheory.jl#64. To make the code efficient, I need to get the correspondence between each vertex in VRepresentation and the indices of inequalities in HRepresentation that generate this vertex.

For example,

julia> H = SimpleHRepresentation([1 1; -1 0; 0 -1], [1, 0, 0])
H-representation
begin
 3 3 integer
 1 -1 -1
 0 1 0
 0 0 1
end

julia> p = polyhedron(H, getlibraryfor(2, Float64))
Polyhedra.SimplePolyhedron{2,Float64}(Nullable{Polyhedra.HRepresentation{2,Float64}}(H-representation
begin
 3 3 real
 1.0 -1.0 -1.0
 0.0 1.0 -0.0
 0.0 -0.0 1.0
end), Nullable{Polyhedra.VRepresentation{2,Float64}}())

julia> V = SimpleVRepresentation(p)
V-representation
begin
 3 3 real
 1 0.0 1.0
 1 1.0 0.0
 1 0.0 0.0
end

For vertex (0, 1) in the VRepresentation, it is the extreme point generated by the first and second inequalities in HRepresentation binding. Therefore the indices of binding inequalities along with vertex (0, 1) is [1, 2]. What I want to get is a list of such indice lists for all vertices. Is there any method available in Polyhedra.jl that can do this? Or do you think it is possible (and meaningful) to add this feature? I would appreciate it a lot if you would like to help me with this.

[blegat]

Hello, we have a code that does something similar here.
It counts the number of halfspaces to see if the point is redundant. It would be interested to add a function to return the list, we just need to find a good name for it :)

[shizejin]

Thanks for replying! If I understand the function isvredundant correctly, it tries to find the redundant points after we have VRepresentation and HRepresentation? I am thinking that, if we can record this information during the transformation form HRepresentation to VRepresentation and then return it, will the efficiency be very different? (Though I think this is not a feature that most people will need, it plays a very important role in my algorithm.) Thanks!

[blegat]

Yes, after every halfspace we add, we generate all the points and then we remove all the redundant ones here.
I would imagine that getting this information at the end of the computation would have a computation time negligible compared to the computation time required to do the representation conversion.
Having this information cached during the computation may be interesting since we add the halfspaces one at a time so we only need to update the information for the new points and for the old points we only need to check the new halfspace.
However, the implementation in Polyhedra.jl is meant to be simple and only make use of existing utilities that are useful outside of the representation conversion algorithm. For instance, isvredundant is relevant outside the context of representation conversion. It just checks if a point is redundant given an H-representation, also the operation of intersecting a V-representation with an halfspace is a well defined operation without the context of representation conversion.
Therefore I would say that you can give a default implemention as with isvredundant but if a polyhedral library already has this information available, it will define a faster one for his type. This will probably not be the case of SimplePolyhedraLibrary though.

[shizejin]

Thanks very much for your detailed explanation!

Yeah I totally agree that adding this feature as a field cached in Representation is very unnatural. I will try to implement my algorithm aka isvredundant to see if there is significant efficiency loss.

Let me leave this issue open for a while, to see if I can write a function doing what you suggested.

Thanks again. I really appreciate your kind and useful suggestions.

[blegat]

This will be addressed by #67