Hi guys, [SOLVED: thanks for the hints!]

how do i show that a primal has multiple solutions if it has a nondegenerate solution and its dual has degenerate?

asked 02 Mar '12, 07:05

secondrate's gravatar image

secondrate
1114
accept rate: 0%

retagged 12 Oct '12, 05:53

yeesian's gravatar image

yeesian
846210

No need to edit the titles to add "Solved". Just "accept" an answer to highlight it and show it answered in the question list.

(24 Mar '12, 10:28) Michael Trick ♦♦

You know the following :

  • If the primal is non degenerated, then you can not exchange a basis variable without the primal solution will change. which may change the objective, even if there are dual degenerated variables or not.
  • Since the dual is degenerated, there exists a non basic variable with reduced cost zero. This variable can be raised or lowered (depending on if it's on lower or upper bound) with a zero cost move. i.e the move in basic variables combined with the move in the variable will result in no change in the objective.
  • You can then do a standard simplex pivot on the dual degenerated variable, use the minimum ratio rule to find the leaving variable. Exchange basis and update the solution. If no leaving variable is found, then you have a ray to construct solutions from.

At least this is the intuitive way to think of it, not sure it's what you are looking for.

link

answered 02 Mar '12, 07:28

Bo%20Jensen's gravatar image

Bo Jensen ♦
5.0k2919
accept rate: 14%

hi bo, i'm a bit confused by what you said...why is it that if the dual is degenerate, there exists a non basic variable with reduced cost zero?

(02 Mar '12, 07:54) secondrate

A primal degenerated basis has a basic variable on a bound i.e in the simple case with x >= 0 => x = 0. A dual degenerated basis means a dual variable (i.e reduced cost) is zero on at least one of the non basic variables. So to answer your question, then it's actually the definition of dual degeneracy :-)

(02 Mar '12, 08:10) Bo Jensen ♦

hi bo, did you mean, a dual degenerate basis has a dual basic variable with value instead? Also, I know that the reduced cost of the primal variables = -(dual variables). so how can you say "a non basic variable with reduced cost zero"?

Hmm, is there a simpler solution to this problem? thanks bo!

(02 Mar '12, 08:17) secondrate

So was this homework? Since Bo has already answered...

Look at the proof of the strong duality theorem. Most proofs are constructive, i.e., given a basic optimal primal solution, the proof shows you how to construct a corresponding complementary basic optimal dual solution. If you look carefully at the case where that dual solution is degenerate, you'll see that the corresponding primal solution has a nonbasic variable with zero reduced cost--dual slacks represent primal reduced costs. If you pivot that variable in, you'll move to a distinct primal solution with the same objective value.

link

answered 02 Mar '12, 11:20

Matthew%20Saltzman's gravatar image

Matthew Salt... ♦
4.7k310
accept rate: 17%

Hey matthew, ok I got that part now. But I'm confused with this "ray" when a leaving solution can't be found.

(02 Mar '12, 11:42) secondrate

Pivoting a nonbasic variable into the basis corresponds to increasing it from its bound value of zero and adjusting the values of basic variables to maintain feasibility of the structural constraints. The ratio test tells the maximum amount that variable can increase before a basic variable violates its bound. Every value of the entering variable up to that point represents a feasible but not basic solution. If the ratio test fails, that just means you can keep increasing the entering variable without bound. If the entering variable has zero reduced cost, the objective doesn't change.

(02 Mar '12, 12:23) Matthew Salt... ♦

Geometrically, increasing the value of a nonbasic variable corresponds to moving along an edge (one-dimensional face) of the feasible region. If the ratio test fails, that edge is a "ray", i.e., you can travel along it forever.

(02 Mar '12, 12:25) Matthew Salt... ♦

Here's another (I think) way to look at it. Since the dual of the dual is the primal, let's flip the question: if the primal solution is degenerate, how do we know the dual has multiple optima? (I'll give the "intuitive graphical" argument; nailing down details may or may not be easy.)

If the primal solution is degenerate, there's at least one constraint binding at the optimum such that if you relax the constraint, the optimum does not move. So the shadow price for relaxation is zero. On the other hand, tightening that constraint will cut off the current optimum. Since we're also assuming the dual solution is non-degenerate, the primal cannot have multiple optima, so cutting off the solution "hurts" the objective value by a nonzero amount ... which means the shadow price for tightening is nonzero. That gives us two different shadow prices for the same constraint, depending on which way we perturb it, so the dual must have multiple solutions.

link

answered 03 Mar '12, 11:28

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k412
accept rate: 19%

(1) If you've received a satisfactory answer, please accept the answer so that the system shows your question as answered.

(2) One possible boundary case (ruled out by your assumptions) is where both primal and dual are degenerate at optimality. In that case, you'll have a primal nonbasic variable with zero reduced cost (because the dual is degenerate), but it could be the case that moving that variable off its bound would force the degenerate basic variable to violate its bound. In that case, you can't tell from the current basic solution whether there are multiple optima.

link

answered 21 Oct '12, 15:41

Matthew%20Saltzman's gravatar image

Matthew Salt... ♦
4.7k310
accept rate: 17%

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×231
×18
×17

Asked: 02 Mar '12, 07:05

Seen: 3,634 times

Last updated: 17 Nov '12, 16:29

OR-Exchange! Your site for questions, answers, and announcements about operations research.