Is the Intersection of an Integral and half-integral polytopes half-integral?

102 Views Asked by At

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?

1

There are 1 best solutions below

1
On

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