Characterization of integral polyhedra

Question

A rational polyhedron $P \subseteq \mathbb{R}^n$ is an integral polyhedron if it is the convex hull of its integer points. That is, if $P = conv(P \cap \mathbb{Z}^n)$.

Equivalently, $P$ is integral if for any $c \in \mathbb{R}^n$, the program $\max\{cx : x \in P\}$ has an integer optimizer.

Now according to the theorems, to show that $P$ is integral, it merely suffices to show that for any $c \in \mathbb{Z}^n$, the program $\max\{cx : x \in P\}$ has an integer optimal value (whenever the optimum is finite).

Why should having an integer optimal value imply that there is an integer optimal solution? The proofs that I read for this use duality and give me no intuition.

Is there a better explanation of why this is true, or some kind of intuition?

Answer 1

Here's a proof (sketch) that doesn't explicitly use duality. More precisely, it replaces duality by a seemingly weaker (and hopefully easily believable) geometric fact, in Step 3 below.

EDIT: But, per the comment, the proof applies only to polytopes, not (unbounded) polyhedra!

Let $P\subset \mathbb R^n$ be any polyhedron polytope such that, for all $c\in \mathbb Z^n$, the (optimal) value of the LP $\max\{cx : x\in P\}$ is an integer.

Lemma 1. $P$ is integral. That is, every extreme point (vertex) of $P$ has integer coordinates.

Proof sketch.

1. Suppose otherwise for contradiction. That is, there exists a vertex $x'$ of $P$ with a coordinate $x'_k$ that is not an integer.

2. Given any cost vector $c\in \mathbb R^n$ such that $x'$ is an optimal solution to the linear program $\max\{c\cdot x : x\in P\}$, say that ``$c\cdot x$ is maximized by $x'$.''

3. We will use the following, hopefully intuitive, geometric fact: the set of vectors $c$ such that $c\cdot x$ is maximized by $x'$ contains a ball of positive volume in $\mathbb R^n$. (Draw some pictures for intuition.)

4. Equivalently, there is a vector $c'\in \mathbb R^n$ and an $\epsilon>0$ such that, for all $d\in \mathbb R^n$, if $\max_i |d_i - c'_i| \le \epsilon$, then $d\cdot x$ is maximized by $x'$.

5. Now define $d' = c'/\epsilon$ (scaling up $c'$ by $1/\epsilon$).

6. Then, for all $d\in \mathbb R^n$, if $\max_i |d_i - d'_i| \le 1$, then $d\cdot x$ is maximized by $x'$. (Here we use Line 4 above, and that $d\cdot x$ is maximized by $x'$ iff $(\alpha d)\cdot x$ is, provided $\alpha > 0$. We take $\alpha=1/\epsilon$.)

7. Define $b$ and $b'$ in $\mathbb Z^n$ by taking $b_i = \lfloor d'_i \rfloor$ for all $i$, and obtaining $b'$ from $b$ by increasing $b_k$ by 1. (Recall that $k$ is such that $x'_k$ is not an integer.)

8. Then $b\cdot x$ is maximized by $x'$ (using $\max_i |b_i-d'_i| \le 1$), and $b\in\mathbb Z^n$, so (by our assumption on $P$) $b\cdot x'$ is an integer.

9. By the same reasoning, $b'\cdot x'$ is an integer. So $(b'-b)\cdot x'$ is an integer.

10. But $(b'-b)\cdot x'$ equals $x'_k$, which is not an integer. $~~~\Box$