<p>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.</p>
<p><em>EDIT: But, per the comment, the proof applies only to polytopes, not (unbounded) polyhedra!</em></p>
<p>Let <span class="math-container">$P\subset \mathbb R^n$</span> be any <del>polyhedron</del> polytope such that, for all <span class="math-container">$c\in \mathbb Z^n$</span>, the (optimal) value of the LP <span class="math-container">$\max\{cx : x\in P\}$</span> is an integer.</p>
<p><strong>Lemma 1.</strong> <em><span class="math-container">$P$</span> is integral.  That is, every extreme point (vertex) of <span class="math-container">$P$</span> has integer coordinates.</em></p>
<p><em>Proof sketch.</em></p>
<ol>
<li><p>Suppose otherwise for contradiction.  That is, there exists a vertex <span class="math-container">$x'$</span> of <span class="math-container">$P$</span> with a coordinate <span class="math-container">$x'_k$</span> that is not an integer.</p>
</li>
<li><p>Given any cost vector <span class="math-container">$c\in \mathbb R^n$</span> such that <span class="math-container">$x'$</span> is an optimal solution to the linear program <span class="math-container">$\max\{c\cdot x : x\in P\}$</span>, say that <em>``<span class="math-container">$c\cdot x$</span> is maximized by <span class="math-container">$x'$</span>.''</em></p>
</li>
<li><p>We will use the following, hopefully intuitive, geometric fact: the set of vectors <span class="math-container">$c$</span> such that <span class="math-container">$c\cdot x$</span> is maximized by <span class="math-container">$x'$</span> contains a ball of positive volume in <span class="math-container">$\mathbb R^n$</span>. (Draw some pictures for intuition.)</p>
</li>
<li><p>Equivalently, there is a vector <span class="math-container">$c'\in \mathbb R^n$</span> and an <span class="math-container">$\epsilon&gt;0$</span> such that, for all <span class="math-container">$d\in \mathbb R^n$</span>, if <span class="math-container">$\max_i |d_i - c'_i| \le \epsilon$</span>, then <span class="math-container">$d\cdot x$</span> is maximized by <span class="math-container">$x'$</span>.</p>
</li>
<li><p>Now define <span class="math-container">$d' = c'/\epsilon$</span> (scaling up <span class="math-container">$c'$</span> by <span class="math-container">$1/\epsilon$</span>).</p>
</li>
<li><p>Then, for all <span class="math-container">$d\in \mathbb R^n$</span>, if <span class="math-container">$\max_i |d_i - d'_i| \le 1$</span>, then <span class="math-container">$d\cdot x$</span> is maximized by <span class="math-container">$x'$</span>. (Here we use Line 4 above, and that <span class="math-container">$d\cdot x$</span> is maximized by <span class="math-container">$x'$</span> iff <span class="math-container">$(\alpha d)\cdot x$</span> is, provided <span class="math-container">$\alpha &gt; 0$</span>.  We take <span class="math-container">$\alpha=1/\epsilon$</span>.)</p>
</li>
<li><p>Define <span class="math-container">$b$</span> and <span class="math-container">$b'$</span> in <span class="math-container">$\mathbb Z^n$</span>
by taking <span class="math-container">$b_i = \lfloor d'_i \rfloor$</span> for all <span class="math-container">$i$</span>,
and obtaining <span class="math-container">$b'$</span> from <span class="math-container">$b$</span> by increasing <span class="math-container">$b_k$</span> by 1.  (Recall that <span class="math-container">$k$</span> is such that <span class="math-container">$x'_k$</span> is not an integer.)</p>
</li>
<li><p>Then <span class="math-container">$b\cdot x$</span> is maximized by <span class="math-container">$x'$</span> (using <span class="math-container">$\max_i |b_i-d'_i| \le 1$</span>),
and <span class="math-container">$b\in\mathbb Z^n$</span>, so (by our assumption on <span class="math-container">$P$</span>) <span class="math-container">$b\cdot x'$</span> is an integer.</p>
</li>
<li><p>By the same reasoning, <span class="math-container">$b'\cdot x'$</span> is an integer.  So <span class="math-container">$(b'-b)\cdot x'$</span> is an integer.</p>
</li>
<li><p>But <span class="math-container">$(b'-b)\cdot x'$</span> equals <span class="math-container">$x'_k$</span>, which is not an integer. <span class="math-container">$~~~\Box$</span></p>
</li>
</ol>

CC BY-SA 4.0
2021-05-13T06:02:17.130Z
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
Karagounis Z
CC BY-SA 4.0
2021-05-13T12:12:35.013Z
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.
Neal Young
CC BY-SA 4.0
2021-05-13T15:56:37.437Z
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.
Chandra Chekuri
CC BY-SA 4.0
2021-05-13T19:09:02.623Z
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.
Karagounis Z
CC BY-SA 4.0
2021-05-13T20:41:56.887Z
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.
Neal Young
CC BY-SA 4.0
2021-05-11T19:58:55.610Z
2021-05-13T12:25:03.070Z
2021-05-13T12:25:03.070Z
Neal Young
<p>A rational polyhedron <span class="math-container">$P \subseteq \mathbb{R}^n$</span> is an integral polyhedron if it is the convex hull of its integer points. That is, if <span class="math-container">$P = conv(P \cap \mathbb{Z}^n)$</span>.</p>
<p>Equivalently, <span class="math-container">$P$</span> is integral if for any <span class="math-container">$c \in \mathbb{R}^n$</span>, the program <span class="math-container">$\max\{cx : x \in P\}$</span> has an integer optimizer.</p>
<p>Now according to the theorems, to show that <span class="math-container">$P$</span> is integral, it merely suffices to show that for any <span class="math-container">$c \in \mathbb{Z}^n$</span>, the program <span class="math-container">$\max\{cx : x \in P\}$</span> has an integer optimal <em>value</em> (whenever the optimum is finite).</p>
<p>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.</p>
<p>Is there a better explanation of why this is true, or some kind of intuition?</p>

CC BY-SA 4.0
2021-05-11T14:51:13.907Z
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.
Neal Young
CC BY-SA 4.0
2021-05-11T15:50:43.680Z
@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.
Chandra Chekuri
CC BY-SA 4.0
2021-05-11T17:48:13.273Z
@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.  (??)
Neal Young
CC BY-SA 4.0
2021-05-11T19:36:21.640Z
@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.
Chandra Chekuri
CC BY-SA 4.0
2021-05-11T19:59:31.130Z
Okay I've tried to formalize this as an answer, below.
Neal Young
<ds.algorithms><optimization><linear-programming><integer-programming>
Characterization of integral polyhedra
Karagounis Z
# Characterization of integral polyhedra

(Asked by: username_0 on 2021-05-11)

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?

**Tags:** ds.algorithms, optimization, linear-programming, integer-programming
> **Comments:**
> **username_1**: 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.  
> **username_2**: @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.  
> **username_1**: @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.  (??)  
> **username_2**: @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.  
> **username_1**: Okay I've tried to formalize this as an answer, below.  

---

## 1 answers

### Answer by username_1 on 2021-05-11. Score: 6 | Accepted answer

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$

> **Comments:**
> **username_0**: 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  
> **username_1**: 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.  
> **username_2**: 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.  
> **username_0**: 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.  
> **username_1**: 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.  

---

