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.

Answer 2

I will decompose the problem of finding facets into 2 parts. First, let us obtain an irredundant representation of the system of inequalities. In the second part, we will identify implicit equalities and eliminate them as candidates for facets. Also thanks to @RobPratt for identifying a deficiency with my earlier answer.

Part 1: Let us assume we are given a system of inequalities (say $Ax \leq b \iff \lbrace{a_i^\top x \leq b_i \rbrace}_{i=1}^{L}$). Suppose we wanted to know if $a_1^\top x \leq b_1$ is redundant or not, we can compute the optimal value (OPT) of following linear program:

\begin{align} OPT = \underset{x\in \mathbb{R}^{n}}{\max{}} &\,a_1^\top x \\ \mbox{s.t.} &\, a_i^\top x\leq b_i, i\in [2, L] \tag{1} \end{align}

If $OPT \leq b_1$, then we know that the inequality $a_1^\top x \leq b_1$ is redundant (and so not a facet) since every point that satisfies the set of inequalities $\lbrace{ a_i^\top x\leq b_i \rbrace}_{i=2}^L$ already obey the inequality $a_1^\top x \leq b_1$. At this stage you must remove the inequality $a_1^\top x \leq b_1$ from the system $Ax \leq b$ to obtain an irredundant represenatation. If on the other hand $OPT > b_1$, then $a_1^\top x \leq b_1$ may be a candidate for a facet of $Ax\leq b$ and so you don't eliminate that inequality. We can repeat this process for the remaining $L-1$ inequalities one by one, to obtain the final set of irredundant inequalities.

Part 2 For the second part, we will assume that $Ax \leq b \iff \lbrace{a_i^\top x \leq b_i \rbrace}_{k=1}^{m}$ does not contain any redundant inequalities. Further denote $P = \lbrace{ x \in \mathbb{R}^n| Ax \leq b\rbrace}$. It may be the case that every $x \in P$ satisfies $a_i^\top x = b_i$ for some $i \in [1, m]$. If the condition holds then the inequality $a_i^\top x \leq b_i$ is an implicit equality and not a facet of $P$. To identify whether inequality is implicit equality or not, I recommend looking at the procedure described in the first answer here(https://cs.stackexchange.com/questions/128505/how-to-calculate-the-dimension-of-a-convex-polyhedron). For convenience I am reposting the relevant bit here. Suppose:

$$\max \{a_i^\top x \mid Ax\leq b\} = \min \{a_i^\top x \mid Ax\leq b\} = b_i,$$

then $a_i^\top x \leq b_i$ is an implicit equality. Whichever inequalities in $Ax \leq b$ are not implicit equalities are the facets.