1

Given an integral polytope $\{x \in \mathbb{R}^n | A_1x \leq b , x\geq 0_n \}$ where the extreme points are integral, and another half-integral polytope $\{x \in \mathbb{R}^n | A_2x \leq b , x\geq 0_n\}$, what are some techniques or theorems to show that

$\{x \in \mathbb{R}^n | \left( \begin{matrix} A_1 \\ A_2 \end{matrix} \right)x \leq b , x\geq 0_n\}$ is half-integral, if it is true?

AspiringMat
  • 2,483
  • 1
  • 17
  • 32

1 Answers1

2

Not even the intersection of 2 integral polytopes is integral!

E.g. consider the polytope $P_1$ being the square which is the convex hull of (0, 0), (2, 0), (0, 2), (2, 2) and $P_2$ being the triangle which is the convex hull of (0, 0), (3, 0), (0, 4): the intersection is a pentagon with 2 of its vertices being (3/2, 2) and (2, 4/3).

--- rk

Dr. Richard Klitzing
  • 4,241
  • Sorry, my question might have come off the wrong way. I understand that not even the intersection of integral polytopes is always integral. What I meant to ask is, what are some sufficient conditions on $A_1, A_2$ for this to hold? For example, if polytope 1 is inside polytope 2, then this holds (trivially). Just wondering if there are other sufficient conditions or common techniques to show this, when it is true. – AspiringMat Feb 03 '20 at 17:33