2
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – Neal Young
    May 11, 2021 at 14:51
  • 1
    $\begingroup$ @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. $\endgroup$ May 11, 2021 at 15:50
  • 1
    $\begingroup$ @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. (??) $\endgroup$
    – Neal Young
    May 11, 2021 at 17:48
  • $\begingroup$ @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. $\endgroup$ May 11, 2021 at 19:36
  • $\begingroup$ Okay I've tried to formalize this as an answer, below. $\endgroup$
    – Neal Young
    May 11, 2021 at 19:59

1 Answer 1

6
$\begingroup$

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$

$\endgroup$
5
  • $\begingroup$ 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 $\endgroup$ May 13, 2021 at 6:02
  • $\begingroup$ 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. $\endgroup$
    – Neal Young
    May 13, 2021 at 12:12
  • 3
    $\begingroup$ 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. $\endgroup$ May 13, 2021 at 15:56
  • 1
    $\begingroup$ 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. $\endgroup$ May 13, 2021 at 19:09
  • 1
    $\begingroup$ 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. $\endgroup$
    – Neal Young
    May 13, 2021 at 20:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.