Existence of pivots that strictly improves the objective value in presence of degeneracy Consider a degenerate LP problem:
$$\min c^Tx \\\text{subject to: }\qquad\qquad\qquad\qquad\qquad$$
$$Ax=1\quad a_{i,j} \in \{0,1\}$$
$$x\ge0$$
Is it safe to assume given an non-optimal initial basis $B_0$, there is always a sequence of pivots for which the objective value strictly improves until optimality? Considering the convexity of an LP implies $c^TB_i^{-1}1\ge c^T\bar B^{-1}1$ where $\bar B$ is the optimal basis, which I can directly infer that $c^TB_i^{-1}1= c^TB_{i+1}^{-1}1$ iff $B_i^{-1}1=B_{i+1}^{-1}1$.
In absence of cycling, which implies given basis index set $S_i$ and $S_{i+1}$ for $B_i$ and $B_{i+1}$ respectively non improving pivots are when $S_{i+1}\not = S_i$ but $B_{i+1}=PB_i$ where $P$ is permutation matrix.
So, the question reduces to determining the necessity of permuting a given basis for strict improvement of the objective value, or is there always an alternative that improves the objective value without permutation of the basis $B_i$ when LP is degenerate?
If so, that should mean if I search for a pivot I should search for a pivot that strictly improves the objective value and exit if no such pivot exists, right?
 A: Let's call $A_{new}$ a submatrix of A from which we've removed all redundant constraints and their corresponding slack variables. The corresponding linear program, $LP_{new}$, is nondegenerate, so any suboptimal basis in $LP_{new}$ has an improving pivot. Choose any sequence of improving pivots.
Now, reconsidering the original linear program, $LP_{old}$, notice that the sequence of pivots we came up with in the previous paragraph is a feasible sequence of pivots here. There's nothing wrong with letting $LP_{old}$'s extra slack variables sit forever in the basis while we ignore them, because they only need to be nonnegative--and we know they're nonnegative because the feasible regions of $LP_{new}$ and $LP_{old}$ are the same.
This argument should apply for all LPs, not just those where
$Ax=1$, $a_{i,j}∈\{0,1\}$. A sequence of strictly improving pivots up to optimality should exist.

EDIT:
It does not follow from this argument that, given $any$ suboptimal basis, there exists an improving sequence of pivots. The argument shows that there exists such a sequence starting from any nondegenerate solution (or from the initial BFS, regardless of its degeneracy), but not from all. Just be aware of this if you're trying to employ a practical search strategy, because it sounds like you may be planning on a local search, which may blindly choose pivots that lead to a dead end.
