Why do the dual cost obtained by .pi seem incorrect, when the upper and lower bounds of variables are defined using "model.addVar"?
AnsweredHello,
I have defined a model called RMP with the following form:
The upper and lower bounds of the variables (lb=0 and ub=1) are defined using "model.addVar" rather than constraints. After optimizing this model, I used .pi to obtain the dual cost for each constraint, which are as follows:
However, this result seems "incorrect" because when I substitute these dual costs into the dual model, I cannot get the same objective function value as RMP, which should be 48. The reason may be the upper bound (ub=1) has a dual cost, but it cannot be retrieved when the bound is not expressed as constraints. But in my opinion, the effect of ub should be reflected by the dual costs of these existing 11 rows, and the correct dual costs for these 11 rows should be C0-C10 in this picture (I get the result by optimizing the ".dlp model" of rmp):
What could be the reason for this error? How can I get "the correct values" as C0-C10 using .Pi?
-
-
Gurobi Staff
Hi Yiran,
There is some degeneracy here. If you remove the bounds on the variables you will get the same solution, meaning the bounds are redundant.
m = gp.read("model.lp")
m.optimize()
first_solution = m.X
m.reset()
for v in m.getVars():
v.ub = float("inf")
m.optimize()
assert all(x1 == x2 for x1, x2 in zip(m.X, first_solution))
assert sum(r*p for r,p in zip(m.RHS, m.Pi)) == 48When using the degenerate bounds you need to alter this last statement to account for reduced costs:
m = gp.read("model.lp")
m.optimize()
assert (
sum(y*b for y,b in zip(m.PI, m.RHS)) +
sum(rc*x for rc,x in zip(m.RC, m.X))
) == 48The dual values can be substituted into the dual model, but using the negative values:
m = gp.read("model.lp")
m.write("dual.dlp")
m.optimize()
d = gp.read("dual.dlp")
for x, v in zip(m.Pi, d.getVars()):
v.lb = -x
v.ub = -x
d.optimize()
assert d.ObjVal == 48To understand why the negatives are used here you can inspect the coefficient matrices, noting that your LP is not in standard form (see Var.Pi):
print(m.getA().todense())
print(d.getA().todense())- Riley
0 -
-
Thank you, Riley.
I have a further question. When there are degenerate bounds, is there a way to reflect the values of m.RC into m.Pi so that I don't have to use m.RC for adjustments and can just use m.Pi to get
sum(y*b for y,b in zip(m.PI, m.RHS)) == 48 ?
0 -
-
Hello sir, I hope you don't mind me adding some more details to the question I asked earlier.
I followed your advice and used .RC to get the reduced cost for each variable. I noticed that the VBasis for variable RV_0 is -2, and its corresponding RC value is -118. This seems incorrect because RV_0 is actually a basic variable in the current optimal solution, as you can see in the results below. Why is there this error?
Thank you!
0 -
-
-
Hi Yiran,
I've updated my previous response to make it simpler, since the reduced cost of non-basic variables is 0.
When there are degenerate bounds, is there a way to reflect the values of m.RC into m.Pi so that I don't have to use m.RC for adjustments and can just use m.Pi to get ...
The easiest way would be to just convert the bounds into constraints then use sum(y*b for y,b in zip(m.PI, m.RHS)). Eg
for v in m.getVars():
if v.ub < float("inf"):
m.addConstr(v <= v.ub)
m.ub = float("inf")I noticed that the VBasis for variable RV_0 is -2, and its corresponding RC value is -118. This seems incorrect because RV_0 is actually a basic variable in the current optimal solution, as you can see in the results below.
If a variable is at its bound then it could be basic, or it could be non-basic. You can't deduce which from the solution values alone. The solver is indicating that it is non-basic, and the other variables are basic, which seems consistent in the context that once you fix the basic variables at their solution values, you can deduce the value of RV_0.
- Riley
0 -
-
Thank you, sir.
The problem is, I have to keep the bounds in variable definitions, and I want to find a way that I don't have to use m.RC for adjustments. Any solutions?
0 -
-
-
Hi Yiran,
No.
- Riley
0 -
Please sign in to leave a comment.
Comments
6 comments