If optimal solution to the primal is degenerate, does it necessarily follow that optimal solution to dual not unique? That is, is uniqueness an unnecessary assumption?
Spin-off from here.
In my Operations Research problem set, our professor required us to prove
"If an optimal solution to the primal is degenerate, then there is at least one alternative optimal solution to the dual."
I found, however, that if we do not assume uniqueness, the statement is false?
I asked by e-mail:
"In the problem set, does the optimal solution to the primal really need not be unique?"
The reply I got:
"Yes. Some LP problems have alternative optimal solutions."
I asked if uniqueness was not needed to conclude an alternative optimal solution to dual and showed the counterexample I linked above (again here).
Reply I got:
"I only said thet in LP, alternative optimal solutions may exist. I am not referring to the problem in the exercise specifically. Please read the statement of the problem again."
I then asked if the OP was equivalent to
If there are several optimal solutions to the primal with at least one of them being degenerate or there is a unique degenerate optimal solution to the primal, then the optimal solution to the dual is not unique?
i.e. (well so I think) uniqueness of degenerate optimal solution to primal is irrelevant.
The reply I got:
"There is an additional assumption in your statement which is not in the problem."
Question: What is the additional assumption?
In the end, we just copied the "proof" of one of our other classmates. Apparently, e was able to prove the statement even though it looks to be false. I don't have the proof with me though.
One of my classmates asked our professor on the day of submission that someone (me) pointed out that if we don't assume uniqueness, the statement doesn't hold. I was kind of sleepy, but iirc, our prof said something that began with
"But that's not what you're trying to show"
or something like that. My classmate didn't respond, and we just moved on. Well, they did.