I am working with a polytope with a very specific structure, namely that it is characterized entirely by placing the variables, or the variables plus constants, or just constants, in a particular order. A completely arbitrary example of this would be $$0\leq x_1 \leq x_2 \leq x_1 + 4 \leq x_3 \leq x_2 + 3 \leq 8 \leq x_3 + 4 \leq x_1 + 9 \leq 100$$ My questions: is there any name for such polytopes, or anything related? Also, is there any nice way to exploit this structure in order to enumerate the vertices of such a polytope?
$\begingroup$
$\endgroup$
1
-
1$\begingroup$ These polytopes are partial cases of the Lipschitz polytopes, defined by a quasi-metric space $(X,\rho)$ and consisting of functions $f$ on $X$ satisfying $f(x)-f(y)\leqslant \rho(x,y)$ for $x,y$ in $X$. Such functions are defined up to additive constant, in other words, we may fix a point $a\in X$ and fix the value $f(a)=0$. In your example you may replace $0,100$ to $x_0,x_0+100$, then each inequality in your chain is of above type. $\endgroup$– Fedor PetrovCommented Sep 24, 2017 at 9:11
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
If I understand correctly, your polytopes are a subset of the polytopes where every inequality has at most two variables with non-zero coefficient.
Those are studied in On the Complexity of Polytopes in $LI(2)$ by Komei Fukuda, May Szedlak, 2017.
(Here "$LI(2)$" denotes exactly those polytopes)
answered Sep 25, 2017 at 8:47