Questions tagged [degeneracy]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2 votes
2 answers
194 views

Proof on Degenerate LP program

do all degenerate LP have have an equivalent non degenerate LP? for example the following is a degenerate LP $$A=\begin{bmatrix}1&0&0&0&1&1&0\\0&1&0&1&0&1&...
someone random's user avatar
1 vote
1 answer
117 views

Avoiding degeneracy in an LP formulation

I assume that "less than or equal to" $\left( \leq \right)$ and "greater than or equal to" $\left( \geq \right)$ constraints avoid degeneracy because each of those has at least one ...
Alexander Mills's user avatar
4 votes
1 answer
76 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 ...
gmn's user avatar
  • 632
1 vote
1 answer
156 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 ...
Samarth's user avatar
  • 173
4 votes
0 answers
66 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-...
Brannon's user avatar
  • 892