I was wondering if the following is true. Suppose that for a certain LP no basic feasible solution is degenerate. Does it follow that this LP has a unique optimal solution?
Asked
Active
Viewed 585 times
1
-
1No. Consider $\max\ x_1$ subject to $0\leq{x_i}\leq1$ for $i=1,2$. – David M. Sep 24 '18 at 00:39
-
Thanks! Do you also know the answer to this one? If the dual problem has a non-degenerate optimal solution, then the primal problem has a unique optimal solution. Whether it's true or false @DavidM. – Keep_On_Cruising Sep 24 '18 at 17:43
-
Post a new question and include your thoughts and attempts! – David M. Sep 24 '18 at 17:49
-
I did :D @DavidM. – Keep_On_Cruising Sep 24 '18 at 20:19
-
@DavidM. Your answer is wrong btw $(0,0)$ is a degenerate basic feasible solution in your example – Keep_On_Cruising Sep 25 '18 at 17:51
-
Can you define “degenerate” in your post? – David M. Sep 25 '18 at 17:54
-
An LP is degenerate if in a basic feasible solution, one of the basic variables takes on a zero value. – Keep_On_Cruising Sep 25 '18 at 18:19
1 Answers
1
The answer is no: a simple counterexample is \begin{equation} \begin{array}{rl} \max\ & x_1 \\ \text{s.t.}\ & x_1 \leqslant 1 \\ & x_2 \leqslant 1 \\ & x_1,x_2\geqslant 0 \end{array} \end{equation}
You object that the solution $(0,0)$ is degenerate, but in fact it is not. Try reviewing the definitions of basic solution and degenerate solution.
(If it really bothers you, you could easily shift the feasible region of my example:\begin{equation} \begin{array}{rl} \max\ & x_1 \\ \text{s.t.}\ & x_1 \leqslant 2 \\ & x_2 \leqslant 2 \\ & x_1,x_2\geqslant 1 \end{array} \end{equation} and the "problem" goes away.)
David M.
- 2,623
-
Yes my thoughts aswell on that last one, but (0,0) is a basic feasible solution of the first example right (because it's a corner point of the polyhedron)? So then it is degenerate because one of the variables of the solution is equal to zero. – Keep_On_Cruising Sep 25 '18 at 23:22
-
@Keep_On_Cruising That’s not the definition of a basic feasible solution. Check the definition—in particular, look at the form of the LP used when BFS is defined. – David M. Sep 26 '18 at 03:31
-
Ik know that it is not the definition of a bfs but there is a unique corner point corresponding to each BFS. So they are equivalent. What am I seeing wrong here? – Keep_On_Cruising Sep 26 '18 at 11:38
-
Extreme points and BFSs are indeed equivalent, but that doesn't mean that $(0,0)$ is a BFS (consider the example above where you shift the polytope). – David M. Sep 28 '18 at 19:54