The general topic is unimodular matrices and integral polyhedra. I am really new to this field and I am studying for an exam in an advanced operations research course. In this case we are always talking about rational polyhedra (defined by linear unequation systems).
There are several equivalent definitions for integral polyhedra. The most intuitive for me is:
Let $P_I = conv( P \cap \mathbb{Z}^n )$. A polyhedron ist integral if $P = P_I$.
This definition is equivalent to the definition:
$P$ is an integral polyhedron if every face contains an integer point.
Now that confuses me. I think I can easily draw a $2$-dimensional convex shape such that every face contains an integer point but the corners (crossing points of the faces) are no integer points. Is that a contraction to the first definition.
Here is another definition which is apparently equivalent and in my intuition even more contradicts the little shape example:
$P$ is an integral polyhedron if $argmax_x\{c^Tx \mid x \in P\}$ is a integer point for every $c \in \mathbb{R}^n$.
I think I can easily choose $c$ such that the maximum is in one of the non-integer corners.
What is wrong with my intuition?
Best Answer
Terminology differs, but "face" is generally not the same thing as "facet". Faces can have any dimension, from zero up to the dimension of the polyhedron itself. For an integral polyhedron, all faces have to contain an integer point, in particular the faces of dimension $0$ (the "corners", or "vertices", or "extreme points"). This means that the "corners" must be integer points themselves.