When I am solving linear programming with lower bound of decision variables is positive I am getting all dual solution zero. How can I get correct dual solution?

asked 16 Jul '16, 03:22

Amit%20Sarkar's gravatar image

Amit Sarkar
136
accept rate: 0%

edited 16 Jul '16, 03:24


When you specify a nonzero lower bound on a variable (doesn't matter if it is positive or negative) or a finite upper bound, those bounds have shadow prices. The catch is that, in a solver, there will not be an explicit dual variable corresponding to each bound. Instead, the reduced cost of the primal variable takes the place of the shadow price (dual value) of a constraint bound.

There are a couple of additional complications. Let's say \(x\) is the primal variable being bounded. If it ends up basic and strictly between its lower and upper bounds (say \(0 \neq L\lt x \lt U \lt \infty \)), the reduced cost of \(x\) will be zero, which is the correct dual value. Had you written the bounds as explicit constraints, neither would be binding. If \(x\) lands on one of its bounds, the constraint involving that bound is binding, and you potentially have a nonzero dual value. (I say "potentially" because it could still be zero if the solution is degenerate.) The catch is that the correct dual variable is either the reduced cost or the negative of the reduced cost, depending on which bound (lower or upper) is binding and whether you are maximizing or minimizing. (Working out the details is left to the reader as an exercise, as my fingers are wearing out typing all this.) Finally, if you have specified both a lower and an upper bound, you need to keep in mind that the reduced cost pertains to whichever one is binding; the shadow price of the other one is zero. If they're both binding (which means they're equal), the reduced cost applies to one and its negative applies to the other.

link

answered 16 Jul '16, 16:12

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k513
accept rate: 19%

edited 16 Jul '16, 16:12

Thank you sir for your answer. My objective is to get the dual solutions from MIP. Step1: I solved MIP. Got the optimal solution. Step2: I relaxed integral constraint for the variables. Set upper bound and lower bound of decision variables as optimal solutions of MIP. Step3: I solved relaxed LP with all variables UB and LB are same.

Output: I am getting reduced cost positive (I.e. same value as in coefficient in the objective function as I am getting dual solution zero for all the constraints) for all basic variables.

(17 Jul '16, 01:42) Amit Sarkar

Below is my code: CPLEX for MATLAB api

cplex.Model.obj = C'; cplex.Model.lb = lb'; cplex.Model.ub = ub'; cplex.Model.A = A; cplex.Model.rhs = B; cplex.Model.lhs = -inf * ones(size(B)); cplex.Model.ctype = vartype; cplex.solve();

sol = cplex.Solution.x; cplex.Model.lb=[cplex.Solution.x]'; cplex.Model.ub=cplex.Model.lb; cplex.Model.ctype = []; cplex.solve(); rc=cplex.Solution.reducedcost; dual=cplex.Solution.dual;

(17 Jul '16, 03:44) Amit Sarkar

Getting a reduced cost that matches the variable coefficient is plausible. Having the reduced costs of all the integer variables match their objective coefficients is less likely but also possible. This raises the twin questions of why you want the dual values of the reduced LP and whether the values you get, while correct, will be useful.

(17 Jul '16, 16:10) Paul Rubin ♦♦
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
×17
×2

Asked: 16 Jul '16, 03:22

Seen: 1,233 times

Last updated: 17 Jul '16, 16:10

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