Characterization of integral polyhedra 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?
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.

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

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'$.''

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.)

Equivalently, there is a vector $c'\in \mathbb R^n$ and an $\epsilon&gt;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'$.

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

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 &gt; 0$.  We take $\alpha=1/\epsilon$.)

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.)

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.

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

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