Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I just read in one of the questions answered by @MikeSpivey that the following table is provided in Sierksma's Linear and Integer Programming: Theory and Practice, Volume 1, page 144.

Primal Optimal Solution                     Dual Optimal Solution
(a) Multiple                     implies    Degenerate
(b) Unique and nondegenerate     implies    Unique and nondegenerate
(c) Multiple and nondegenerate   implies    Unique and degenerate
(d) Unique and degenerate        implies    Multiple

I wonder if the information provided in this table is provided based on the assumption that matrix A has full rank.

share|improve this question

1 Answer 1

An LP is degenerate if in a basic feasible solution, one of the basic variables takes on a zero value. Degeneracy is caused by redundant constraint(s) and could cost simplex method extra iterations, as demonstrated in the following example.

$max \space z=x_{1}+x_{2}+x_{3}$

$x_{1}+x_{2} \leq 1$

$-x_{2}+x_{3} \leq 0$

$x_{1},x_{2},x_{3} \geq 0$

Note that constraints $x_{2} \geq 0$ follows from constraints $-x_{2}+x_{3} \leq 0$ and $x_{3} \geq 0$, and is thus redundant. You can check that after iteration 2, the value of the objective function remains the same $z = 1$. Due to degeneracy, basis change does not cause the iteration to follow an edge; we are still in the same vertex.

The example was taken from here An Example of Degeneracy in Linear Programming

This example shows that redundancy may occur even if matrix $A$ has full rank.

share|improve this answer
    
Thank you for your reply. In the example you provided matrix A=[1 1;-1 1] has full rank, and yet we have degeneracy. Is there anything I am missing? –  Quick Dec 15 '11 at 1:48
    
@Quick: thanks, you are right, I fixed the answer, so looks like we cannot make connection between redundancy and matrix $A$ with no full rank, and A = [1 1 0; 0 -1 1] –  com Dec 15 '11 at 7:36

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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