Questions tagged [degeneracy]
The degeneracy tag has no usage guidance.
3
questions
4
votes
1
answer
58
views
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 ...
- 429
1
vote
1
answer
87
views
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 ...
- 175
4
votes
0
answers
49
views
bilinear problem proof for NP-completeness of degeneracy check
In the paper "Some NP-complete problems in linear programming" (https://doi.org/10.1016/0167-6377(82)90006-2), there are several proofs given to show that testing for degeneracy in LPs is NP-...
- 585