= Full-dimensional relaxation of integer inequalities
{title2=$P_\varepsilon=\{x:Ax\geq b-\varepsilon\mathbf1\}$}
For an integer <linear polyhedron> $P=\{x\in\mathbb R^n:Ax\geq b\}$ with coefficients bounded by $U\geq1$, put $D=[(n+1)U]^{n+1}$ and $0<\varepsilon<1/D$. If $x_0\in P$, every $h$ with $\|h\|_2\leq\varepsilon/(nU)$ satisfies $A_i h\geq-\sqrt n U\|h\|_2\geq-\varepsilon$. Thus $P_\varepsilon$ 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\geq0$, $A^T\lambda=0$, $\mathbf1^T\lambda=1$ and $b^T\lambda\geq1/D$. A point of $P_\varepsilon$ would give $0=\lambda^TAx\geq b^T\lambda-\varepsilon>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.
Back to article page
