9
$\begingroup$

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?

$\endgroup$

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
1
  • 3
    $\begingroup$ Your statement that the list of facets will be very long is factually incorrect. The facets of a system of linear inequalities can only be from the set of inequalities specified in the system, so they will in the worst case not exceed the number of inequalities in the system. $\endgroup$
    – batwing
    Commented Dec 4, 2020 at 21:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.