Operations Research Stack Exchange is a question and answer site for operations research and analytics professionals, educators, and students. It only takes a minute to sign up.
Sign up to join this community
Is it always possible to escape a degenerate point by a single pivot, or is it possible that several pivots are required? In other words is it possible to get away from a degenerate point by a single pivot regardless of which of the possible bases (given the point one is currently at) one currently has? If no, is there an upper bound on the number of pivots needed?
Edit: What is the minimum number of pivots for an omniscient user to escape a degenerate point?
Let's say you start with $n$ "natural" variables and $m$ inequality constraints (so $m$ slacks), and you are at a degenerate vertex ($V$). Degeneracy means that more than $n$ of the variables are 0 (implying that one or more basic variables are 0). It will be useful to think in terms of binding constraints. A constraint is binding if its slack is 0, and we can think of the "natural" variables as being slacks for the sign constraints $x\ge 0.$
Before proceeding, let's note that any set of constraints that intersect at a vertex of the feasible region corresponds to a basic feasible solution. It's a basic solution because only one point satisfies those constraints as equalities, and it is feasible because, well, the vertex is feasible.
Now pick a vertex that is adjacent to $V$ and construct a basis for it. The edge connecting the vertices is defined by a set $S$ of $n-1$ constraints that are binding at both endpoints, meaning their slacks are zero at both endpoints. (Additional redundant constraints can be binding along the edge, but they will not affect what follows.) One new constraint ($C$) intersects the new vertex but not $V$, meaning its slack is positive at $V.$
So to get from $V$ to the new vertex, you need to pivot the slack corresponding to $C$ out of the basis, pivot any of the $n-1$ slacks corresponding to constraints in $S$ out of the basis if they are currently in it, and that's about it. Since any combination of binding constraints that intersect at $V$ form a basis, you can just replace any of the $n-1$ slacks in $S$ with the slack from some other binding constraint, one by one, then pivot the slack for $C$ out of the basis. So the omniscient user should be able to do this in at most $n$ pivots.
