4
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ Are you asking whether we can bound the number of pivots required by an omniscient user who chooses the variables to enter/leave the basis, or the number of pivots required by a version of the simplex algorithm? The latter may depend on the specific implementation of the algorithm, and in particular what anti-cycling provisions it contains. $\endgroup$
    – prubin
    Commented Jul 6, 2022 at 15:23
  • $\begingroup$ All pivots will be primal degenerate for the problem min c'x, Ax=0, x>=0 in the primal simplex. And to the best of my knowledge their can be an exponential of them. $\endgroup$ Commented Jul 6, 2022 at 18:17
  • $\begingroup$ @prubin : Yes, the minimum number of pivots for an omniscient user to escape a degenerate point. $\endgroup$
    – gmn
    Commented Jul 7, 2022 at 8:52

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.