How to get all the facet inequalities from a set of valid inequalities?

Question

For a given set of valid inequalities $\cal V$ $$ \left\{\sum_{i}^n w_k x_i + c_k \le 0\right\}_k $$ we can obtain a polyhedron $P$ in $n$-dimensional space. It's known that the polyhedron $P$ can be either represented by its vertices, which is named as the V-representation, or represented by its facet inequalities and equalities, which is called the H-representation. To switch from those two representations, we can utilize different algorithms and packages like lrs, cdd.

Definitely we can calculate the V-representation from the set of valid inequalities $\cal V$, and then switch to the H-representation to obtain all the facet inequalities. Well, this indirect approach is extremely time-consuming sometimes.

So the question is, is there a better way to get all the facet inequalities from a set of valid inequalities?

Answer 1

I believe the answer to your question is principally "no." You mention these implementations, and there are some more, like porta or polymake, but in principle, this is an enormously resource-consuming enumeration, and the list of facets will be very long, maybe too long.

Yet, it may depend on your use case. In optimization practice, you almost never need access to all the facets explicitly, but an implicit access suffices. When you can separate a violated inequality, you may still get all the info you "need." from a computational standpoint.

When you are more into theory and really want to see all the facets, then you will consider small instances/polyhedra anyway (mainly to get an intution to prove something), and then the packages you list are (I think) the way to go.