Questions tagged [degeneracy]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
4 votes
1 answer

Upper bound on number of pivots to escape a degenerate point

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 ...
user avatar
  • 429
1 vote
1 answer

Dual solution when solving a primal degenerate LP with the interior point algorithm

Say, we're working with an LP that is primal degenerate (optimal solution is at a vertex but with multiple bases) and not dual degenerate (optimal solution is not at a face). If we were to solve it ...
user avatar
  • 175
4 votes
0 answers

bilinear problem proof for NP-completeness of degeneracy check

In the paper "Some NP-complete problems in linear programming" (, there are several proofs given to show that testing for degeneracy in LPs is NP-...
user avatar
  • 585