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 an intuition. Suppose that some extreme point $x$ of the polytope (that is, a vertex of $P$) is not integral. Let $c$ be any vector such that $x$ is a unique maximizer of $c x$ in $P$. (It must exist if $c$ is an extreme point.) If $c\cdot x$ is not integer, you are done, so assume otherwise. Then let $c'$ be obtained from $c$ by a random infinitesimal perturbation of every coordinate. Then (i) the probability that $c'\cdot x$ is an integer is zero, and (ii) $x$ is also a unique maximizer of $c'\cdot x$ in $P$. So you are done. May 11, 2021 at 14:51
• @NealYoung in your explanation the perturbed vector $c'$ need not be an integer vector even if $c$ is. The OP is asking about the Edmonds-Giles theorem which is not as straightforward. A simpler version is that for each $c$ rational, $\max\{c x : x \in P\}$ is attained at an integer vector. May 11, 2021 at 15:50
• @ChandraChekuri Oh right. Okay, assume $c\in \mathbb Z^n$ above, take $c'= M c$ for a very large integer $M$. Now take any coordinate $i$ such that $x_i$ is not an integer, and obtain $c''$ from $c'$ by adding 1 to $c'_i$ (and leaving all other coordinates unchanged). Then (i) $c''x$ is not an integer, and (ii) $x$ is also a unique maximizer of $c''x$ in $P$. And $c''$ is integral. (??) May 11, 2021 at 17:48
• @NealYoung Yes, that works and is the right intuition. One has to argue that for sufficiently large $M$ the $+1$ in one coordinate does not matter much as far as the cone of directions for which $x$ is the optimum solution. May 11, 2021 at 19:36
• Okay I've tried to formalize this as an answer, below. May 11, 2021 at 19:59

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

• I really like this argument and I think I understand the intuition now. Thank you. But I wanted to note: your definition of an integral polyhedron isn't quite right. For example if $P = \{(x,y) : x = 1/2\}$, then all extreme points have integer coordinates, because there are none. We can say instead that $P$ is integral if every minimal face contains an integral point. But this is an edge case and I'm sure things can be made to work. Thanks again May 13, 2021 at 6:02
• Oh, good point. This is not a full answer because the proof only applies to polytopes. I wonder if it can be extended to unbounded polyhedra. May 13, 2021 at 12:12
• Edmond-Giles theorem is for unbounded polyhedra. J. Edmonds and F. R. Giles, A min-max relation for submodular functions on graphs, Ann. Discrete Math. l:B-204 (1977). There are technicalities in handling polyhedra vs polytopes. Schrijver's books show all the details. May 13, 2021 at 15:56
• Your proof works for any 'pointed' polyhedron. That is, it works when every face of the polyhedron contains a vertex. Also, if $P$ has even a single vertex, then it is pointed. May 13, 2021 at 19:09
• The general case looks substantially different! E.g. consider some rational polyhedron $$P=\{( x_1,x_2) \in \mathbb R^2 ~|~ a_1 x_1 + a_2 x_2 = b\}.$$ Assume WLOG by scaling that $a_1, a_2\in \mathbb Z$. Then this polyhedron is integral iff $b$ is an integer multiple of $\text{gcd}(a_1, a_2)$. If it isn't, then, by taking $(c_1, c_2) = (\alpha a_1, \alpha a_2)$, where $\alpha=1/\text{gcd}(a_1, a_2)$, we get an LP $\max\{cx : x\in P\}$ with non-integer optimal value. May 13, 2021 at 20:41