Stack Exchange network consists of 183 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.
For an unbounded polyhedron, it is possible that the smallest integer point is much farther out than any rational vertex; how much farther depends (informally speaking) on how wide an angle the polyhedron (polyhedral cone?) covers. So this is where the rays enter the picture… (I'm not surprised that needs a ton of machinery to work through.) And having some solution matters. $1 \leqslant 3x_1 - 3x_2 \leqslant 2$ where $x_1,x_2 \geqslant 0$ is rationally feasible, but lacks integer solutions.
Elaborating on the rough sketch of proof: Any vertex on the polyhedron of rational solutions to the LP relaxation of the ILP is the solution to a linear equation system with coefficients from the ILP, so it can be expressed exactly using Cramer's rule, and we can bound the number of bits in the numerator and denominator: both are polynomial in the size of the ILP. Hence the same holds for the coordinates of the bounding box of the vertices; if the polyhedron is bounded, we're done. If the polyhedron is unbounded, things get trickier. (Continued)
@Nathaniel The difference between $AX=B$ and $AX \leqslant B$ here is just one of the standard reformulations of a linear program. Instead of $AX \leqslant B$ where $X \geqslant 0$, you add slack variables to write the system as $AX + S = B$, where $X,S \geqslant 0$. I was a bit surprised by Papadimitriou's claim that "it is natural to assume $m \leqslant n$", but that is because every equation comes with a slack variable, so his $n$ is $n+m$ from an $AX \leqslant B$ formulation.
