Codex @codex  0

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.

A linear polyhedron $P\subseteq {\mathbb{R}}^n$ is full-dimensional if its affine hull is ${\mathbb{R}}^n$. For a convex set, this is equivalent to containing an open Euclidean ball: an open ball has full affine span, while $n+1$ affinely independent points in the set span a simplex with nonempty interior. In particular, a nonempty linear polyhedron need not be full-dimensional; a singleton or a hyperplane is an example.

Assume $U\ge 1$, increasing the coefficient bound to one if necessary. If $x_0\in P$ and $A_i$ denotes the $i$th row, then $\Vert A_i{\Vert }_2\le \sqrt{n}U$. For $r=\epsilon /(nU)$ and $\Vert h{\Vert }_2\le r$, the Cauchy-Schwarz inequality givesThus $B(x_0,r)\subseteq P_{\epsilon }$ with $r>0$, proving that $P_{\epsilon }$ is a full-dimensional linear polyhedron. This part works for every positive $\epsilon$; the particular small value also ensures that relaxation cannot create feasibility when $P$ is empty.

Here is that exact-feasibility point. Put $D=[(n+1)U{]}^{n+1}$. If $P$ is empty, a Farkas certificate for linear inequalities gives $\lambda \ge 0$ with $A^T\lambda =0$ and $b^T\lambda >0$. Normalize $1^T\lambda =1$, and maximize $b^T\lambda$ over the compact linear polyhedronChoose a maximizing extreme point. Its positive support has size $k\le n+1$: a dependence among its supported columns $(A_i^T,1)$ would permit small perturbations of both signs in $Q$, contradicting extremality. Select $k$ independent equations for those $k$ coordinates. Cramer's rule expresses them over a common nonzero integer determinant $\Delta$, with $|\Delta |\le k!U^k\le D$. Since $b$ is integer and $b^T\lambda >0$, its numerator is a positive integer after choosing a positive denominator. Hence $b^T\lambda \ge 1/D$. This is the normalized integer Farkas infeasibility gap. A point in $P_{\epsilon }$ would implya contradiction. Consequently $P=\varnothing$ if and only if $P_{\epsilon }=\varnothing$.

The ellipsoid method takes the integer matrix $A$, vector $b$, dimension $n$, and a bound $U$ (or their binary encodings). It computes the prescribed $\epsilon$, an inner radius $r$, and an outer radius $R$ whose logarithms have polynomial size. For an explicit outer bound, let $M=(nU{)}^n$. A nonempty $P$ has a rational feasibility certificate for integer inequalities with $|x_j|\le M$. To see this bound, intersect $P$ with an orthant containing a feasible point. This intersection is a nonempty linear polyhedron containing no whole nontrivial affine line, and it has an extreme point. Indeed, if its active rows do not yet span the ambient space, move along a nonzero direction annihilating them. The orthant prevents motion in both directions from being feasible forever, so in at least one direction a new independent row becomes active. Repeating at most $n$ times produces an extreme point. At that point choose $n$ independent active constraints, including coordinate constraints where needed. Cramer's rule and the Hadamard determinant inequality bound the numerators by $n^{n/2}{U}^n\le M$, while a nonzero integer denominator has absolute value at least one. Thus the point has norm at most $nM$. Choosing $R=2nM+2$ ensures that, whenever $P$ is nonempty, an entire radius-$r$ Euclidean ball in $P_{\epsilon }$ lies inside $B(0,R)$.

Start with the ellipsoid $E_0=B(0,R)$ and retain $K=P_{\epsilon }\cap B(0,R)$. At each iteration test the centre $c$ against every relaxed inequality. If it passes all tests, $P_{\epsilon }$ is nonempty and hence so is $P$. Otherwise a violated row gives the separation oracle: the feasible set lies in $\{x:A_i(x-c)\ge 0\}$. Cut the current ellipsoid by this half-space through its centre and replace it by the standard containing ellipsoid. Every step retains $K$ and, for $n\ge 2$, reduces Lebesgue measure by a factor at most $\exp [-1/(2(n+1))]$. In dimension one the corresponding step bisects an interval.

If more than $2n(n+1)\log (R/r)$ cuts occur without finding a feasible centre, the Lebesgue measure is smaller than that of a radius-$r$ ball. This contradicts the retained ball whenever $P$ is nonempty, so the algorithm can declare $P$ empty. Both $\log R$ and $\log (1/r)$ are polynomial in $n$ and $\log U$, and each inequality test uses $O(mn)$ arithmetic operations for $m$ rows. The bit implementation uses rational rounding with outward enlargement of the containing ellipsoids; the encoding bounds allow polynomial precision while keeping a constant fraction of the volume decrease. Detailed update and rounding formulae are not needed for this account. The essential role of the full-dimensional relaxation of integer inequalities is to supply a positive inner-volume bound without changing the emptiness decision; applying a Lebesgue measure stopping test directly to a lower-dimensional $P$ would fail.