Full-dimensional relaxation of integer inequalities ($P_{\epsilon }=\{x:Ax\ge b-\epsilon 1\}$)

For an integer linear polyhedron $P=\{x\in {\mathbb{R}}^n:Ax\ge b\}$ with coefficients bounded by $U\ge 1$, put $D=[(n+1)U{]}^{n+1}$ and $0<\epsilon <1/D$. If $x_0\in P$, every $h$ with $\Vert h{\Vert }_2\le \epsilon /(nU)$ satisfies $A_{i}h\ge -\sqrt{n}U\Vert h{\Vert }_2\ge -\epsilon$. Thus $P_{\epsilon }$ contains a positive-radius Euclidean ball and is a full-dimensional linear polyhedron. If $P$ is empty, the normalized integer Farkas infeasibility gap gives $\lambda \ge 0$, $A^T\lambda =0$, $1^T\lambda =1$ and $b^T\lambda \ge 1/D$. A point of $P_{\epsilon }$ would give $0={\lambda }^{T}Ax\ge b^T\lambda -\epsilon >0$, a contradiction. Consequently this relaxation preserves emptiness and supplies the inner-volume bound needed by the ellipsoid method, even when $P$ has empty interior.