Prove $\exists\bar{b}$ s.t. every solution in polyhedron $P = \{x | Ax \ge \bar{b}\}$ is nondegenerate I'm doing an exercise in the book "Introduction to Linear Optimization" and be stuck in this problem. Can anyone here help me solve this. I really appreciate all your help.


Consider a polyhedron $P = \{x|Ax \ge b\}$. Given any $\epsilon \gt 0$, show that there exists some $\bar{b}$ with the following properties:
    (a) The absolute value of every component of $b - \bar{b}$ is bounded by $\epsilon$
    (b) Every basic feasible solution in the polyhedron $P = \{x|Ax \ge \bar{b}\}$ is nondegenerate.


Thanks so much.
 A: If every BFS is nondegenerate, Simply choose $\bar{b} = b$.
Assume that $x$ is degenerate, by definition this means that more than $n$ of the constraints are active at $x$. Say $k$ constraints are active at $x$ What we have to show here is that you can "push" the redundant constraints away from the solution.  But for each $k-n$ of these constraints you can always push $b$ just a little bit so that this constraint is not active anymore.
A: I just worked this problem and it took me a good day to do it so I figured I'd post my answer since I too looked to stack exchange for an answer. Given $\epsilon>0$ define $\vec{\epsilon}:=(\epsilon,...,\epsilon^m)$. Fix a basis $a_{i_{1}},...,a_{i_{n}}$ and $a_{i_{n+1}}$ not in the basis. Then for some $c_{1},...,c_{n}$ we have that $a_{i_{p}}=\sum_{\ell=1}^{n}c_{\ell}a_{i_{\ell}}$. Hence, if $x$ if a degenerate basic feasible solution of $Ax\geq b-\vec{\epsilon}$ then
\begin{equation}
\epsilon^{i_{n+1}}-b_{i_{n+1}}=a_{i_{n+1}}x=\sum_{\ell=1}^{n}c_{\ell}a_{i_{\ell}}x=\sum_{\ell=1}^{n}c_{\ell}(b_{i_{\ell}}-\epsilon^{i_{\ell}})
\end{equation}
In other words, $\epsilon$ is a root of the polynomial
\begin{equation}
p(z)=z^{i_{n+1}}+\sum_{\ell=1}^{n}c_{\ell}z^{i_{\ell}}-\sum_{\ell=1}^{n}c_{\ell}b_{i_{\ell}}-b_{i_{n+1}}
\end{equation}
As there are only finitely many of these polynomials we can pick $\epsilon'>0$ s.t. if $\epsilon\in(0,\epsilon')$ then $\epsilon$ is a root of none of these polynomials. Thus, the polyhedron $P(\epsilon)=\{x:Ax\geq b-\vec{\epsilon}\}$ is non-degenerate and non-empty - since $P$ is non-empty - if $\epsilon\in(0,\epsilon')$.
