8
$\begingroup$

Suppose you have a set of points $v_1,\ldots,v_n$, which are the vertices of the polytope $P=\operatorname{conv}\{v_1,\ldots,v_n\}$ and a linear inequality $a^\top v \leq b$.

What would be a linear program (or integer program if this is needed) that is feasible if and only if $a^\top v \leq b$ is a facet of $P$?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ all points must be on one side of the inequality, at least a certain number of points (dimension of the polytope many) must fulfill it with equality... the second part (the "counting") probably involves binary variables... $\endgroup$
    – Marco Lübbecke
    Apr 9, 2020 at 11:47
  • 1
    $\begingroup$ yes but the difficult part is to encode the counting of the independent dimension of the points. Maybe there is also a charaterization, which is easier to encode? $\endgroup$
    – user3680510
    Apr 9, 2020 at 12:34
  • $\begingroup$ I see. But when you know that your points are vertices (only), then the correct number on the same face implies affine independence, doesn't it? $\endgroup$
    – Marco Lübbecke
    Apr 9, 2020 at 12:53
  • 1
    $\begingroup$ i think no? Take the unit cube of dimension $n$ and the constraint $x_1 + x_2 \geq 0$, then there are $2^{n-2}$ vertices on the face, but the dimension is still $n-2$ and not $n -1$. $\endgroup$
    – user3680510
    Apr 9, 2020 at 13:08
  • 1
    $\begingroup$ I don't see why there are $2^{n-2}$ vertices on the face. Could you elaborate? $\endgroup$
    – Rolf van Lieshout
    Apr 9, 2020 at 14:15

2 Answers 2

Reset to default
5
$\begingroup$

I will assume that $P$ strictly contains the origin, if not we can simply translate all the vertices of $P$ appropriately. This is possible since one of the comments said that we can assume that $P$ is also full-dimensional. Consider the polar polytope of $P$ denoted by $P^0$, then \begin{equation} P^0 = \lbrace{ x \mid v_i^\top x \leq 1, \, \forall i = 1, 2 , \dotsc, n \rbrace} \end{equation} If my memory serves me correctly, there is a result concerning polar polyhedra that says that there is a 1:1 correspondence between facets of $P$ and vertices of $P^0$ (due to the lockdown I could not find a good reference to post here). This means that it reduces to check whether the $a$ in the inequality $a^\top v \leq b$ in OP corresponds to a vertex of $P^0$. Of course, some scaling issues would need to be handled. If $a$ is a vertex, the also check whether $b = \underset{x \in P}{\text{max}} \,\, a^\top x$, otherwise the inequality does not touch $P$.

Finally, you can refer to my earlier answer to a question (Quadratic programming using CPLEX: how to check whether candidate is an extreme point?) on how to pose the problem of determining whether a given point is a vertex as a sequence of linear optimization problems.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I found it in the script Discrete Geometry I of Prof. Günther M Ziegler, you can search for it online. It is Theorem 2.53 (Polarity for polytopes). $\endgroup$
    – user3680510
    Apr 10, 2020 at 13:06
  • $\begingroup$ thank you very much this leads to a correct answer. If you add the $n$-optimization problems you wrote down in your linked answer to one big problem, and dualize them (to get rid of the inner maximation terms) and add the constraint that the objective value of each must be 0, then i think one arrives at a linear program which satifies the requirements of the questions. The size is however very large O(number of verticies times number of dimensions). $\endgroup$
    – user3680510
    Apr 10, 2020 at 13:49
  • $\begingroup$ I do not think you can avoid formulating a Linear Program that is smaller than O(number of vertices times), because you have specified the polytope P in Vertex representation, and not H representation. I myself am curious if there is some way to reduce dependence on number of dimensions. $\endgroup$
    – batwing
    Apr 10, 2020 at 15:49
2
$\begingroup$

I doubt whether it is possible check whether an inequality is a facet using an (integer) linear program, because it requires counting the number of affinely independent points in some set. The reason why I suspect this cannot be done is that in the least you would need to be able to check whether a set of points $\{v_1,v_2,...,v_m\}$ is linearly independent. To do so, you would need to check whether the equation

$$x_1v_1+x_2v_2+...+x_mv_m = \mathbf{0}$$

has a non-trivial solution, which translates to $\mathbf{x}\neq 0$. Such "not equal" constraints cannot be expressed in integer linear programs.

Improve this answer
$\endgroup$
5
  • $\begingroup$ We can assume that $P$ is full dimensional, how does this easy linear program look like? $\endgroup$
    – user3680510
    Apr 9, 2020 at 13:29
  • $\begingroup$ I added an integer linear program which I believe does the trick. I incorrectly stated that it could be done using a purely linear program. I followed Marco's suggestion, but maybe I am missing something? $\endgroup$
    – Rolf van Lieshout
    Apr 9, 2020 at 13:53
  • $\begingroup$ Yes but the integer program is still only couting the vertices, but this is not enough for it to be a facet, see the counter example in the comments of the question. $\endgroup$
    – user3680510
    Apr 9, 2020 at 13:56
  • $\begingroup$ I think I understand your point. I was counting the number of vertices on the face but not the number of affinely independent points. I will edit my answer. $\endgroup$
    – Rolf van Lieshout
    Apr 9, 2020 at 14:41
  • $\begingroup$ yes exactly and this is the difficult part to encode. But maybe this is also not the right certificate to be a facet for this task. I tought about the charaterization that an inequality is a facet if it cannot be written as the sum of two other non trivial inequalities. But this basically leads to the same problem, that one needs to encode a not equal. $\endgroup$
    – user3680510
    Apr 9, 2020 at 15:04

Your Answer

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

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