The linear problem is : minimize (cost) with optimal value = 100 $ . The cost is always >=0 in my program. Also, a constraint in my program that has the form x <= 0, has a dual value of -500 $. This means that if the constraint becomes x <= 1, then the objective will become -400 $, correct? But how can this be possible, since the objective functions cannot be negative?

However, when I run the linear program with x <= 1 (and all else same), my objective is 20. We would expect however to be -400 since this is what the dual value of that constraint indicated.

Is there an explanation on this weird behaviour ?

asked 08 Aug '14, 12:07

spyimp's gravatar image

spyimp
4118
accept rate: 0%

edited 08 Aug '14, 12:17


Is the variable x at its bound in both solutions? The reduced cost is a rate (change in objective per unit change in variable) and only valid as long as the current basis remains optimal. If x is basic in the new solution (indeed, if any basis change occurred), all you can really say easily is that the new objective value will be less than or equal to the old one.

link

answered 08 Aug '14, 13:38

Matthew%20Saltzman's gravatar image

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

edited 08 Aug '14, 19:28

Mathew thanks. I write it more precisely.

minimize f(x,y,z), where f(x,y,z)>=0 cost function, with optimal value $100. One of the constraints says forces x to be zero ie x=0 . The dual value of this constraint is (minus)$500, which means that if the 0 becomes 1 , then the objective function optimal value (ie $100) will increase by (minus)$500. Also the reduced cost of x is 0.

So I re-run the same program with the only change being that the constraint is x=1 instead of x=0. And although I would expect the optimal value to be 100-500 = -$400, it turns out to be $20. Ofcourse, the objective is >=0, so it could not turn out to be -$400. Then, how was it possible for the dual of x=0 to be -$500, knowing that the objective cannot become negative?

I thought that the dual of a constraint shows the change in the objective for a marginal change in the right-hand-side of the constraint.

The problem is solved optimally ie no infeasibilities there.

(10 Aug '14, 12:57) spyimp
1

The dual value doesn't say that increasing x by one decreases the objective by 500. It says that as you start increasing x, the rate at which the objective falls is 500 per unit change in x. That rate is valid only for changes in x that don't change the optimal basis. The distance that you can move x at that rate without changing the basis might be very small (might even be zero in case of degeneracy). If the basis changes, the multiplier on the constraint you are moving can change. At some point, the bound on x might even become slack, in which case, the multiplier would become zero.

(10 Aug '14, 20:07) Matthew Salt... ♦

Thank you. I write all the information.

Linear-All-Continuous problem: min f(w,y,z)=cw+dy+ez, where c,d,e constants, and w,y,z decision variables and f(w,y,z) ≥ 0. One constraint says x=0, where 'x' is one decision variable that is not part of the objective function. At the optimum: f(w,y,z)=100, and dual value of constraint 'x=0' is -500. Also the reduced cost of 'x' is zero.

Observations:

  1. Since we have x=0 at the optimum, the variable x is nonbasic.
  2. Since at the optimum the reduced cost of x is zero, we infer that if x becomes '1' then we expect to see no change in the objective function optimal value.
  3. Since at the optimum the dual value of the constraint 'x=0' is -500, this means that per unit increase of x, the rate at which the optimal objective reduces is 500. So if constraint 'x=0' becomes 'x=1' (= unit change), the optimal objective will reduce from 100 to -400.
  4. Observation 3 implies that a unit increase in x, will make the optimal objective negative ie from 100 it will go to -400. How can this be possible , given that f(x,y,z) is always ≥ 0?
  5. While observation 3 tells us that we expect to see no change in the optimal objective function from a unit increase in x, the observation 4 tells us that there will be a big change! Why is that?

I re-solved the exact same problem with one change only. The constraint 'x=0' becomes 'x=1'. At the optimum I get f= 20, and reduced cost of x is zero. The dual value of the constraint 'x=1' is -30 ie it changed.

Observations:

  1. Since at the optimum it is x=1, the variable 'x' is now basic. So previously it was nonbasic and now it is basic.
  2. According to observation 2, we would expect no change in the optimal objective. According to observation 3, we would expect to see the optimal objective to go to -400. However, nothing of these happened. Why?
(11 Aug '14, 17:04) spyimp
1

1. x=0 doesn't necessarily imply that x is nonbasic. The fact that the RC is 0 actually suggests otherwise, but the possibility of degeneracy and multiple optima means one can't tell for sure without getting a list of basic variables.

2.-5. No, it's much more complicated than that. First, RC only indicates the rate of objective change as you start to move x. It tells you nothing about how far you can move x while sustaining that rate of objective change. There's more, but the comment is too short for a full explanation.

6. x=1 doesn't imply that x is basic. You've changed the bounds on x.

(11 Aug '14, 18:26) Matthew Salt... ♦

Is it the case that your variables are all nonnegative and the x=0 and x=1 constraints are explicit constraints in the model? In that case, you can think of the x=a constraint as two inequality constraints, x >= a and -x >= -a. That might help you see how the usefulness of the multiplier is limited. (In fact, try formulating your problem this way and see what multipliers you get.) Also, you need to understand degeneracy, which is certainly an issue here. You have three variables (x and two slacks) at least two of which are zero and at least two of which are basic.

(11 Aug '14, 18:43) Matthew Salt... ♦
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
×190
×20
×17

Asked: 08 Aug '14, 12:07

Seen: 759 times

Last updated: 13 Aug '14, 05:44

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