Skip to main content

Why do the dual cost obtained by .pi seem incorrect, when the upper and lower bounds of variables are defined using "model.addVar"?

Answered

Comments

6 comments

  • Riley Clement
    Gurobi Staff 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)) == 48

    When 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))
    ) == 48

    The 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 == 48

    To 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
  • Yiran Wang
    Conversationalist
    First Question

    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
  • Yiran Wang
    Conversationalist
    First Question

    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
  • Riley Clement
    Gurobi Staff Gurobi Staff

    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
  • Yiran Wang
    Conversationalist
    First Question

    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
  • Riley Clement
    Gurobi Staff Gurobi Staff

    Hi Yiran,

    No.

    - Riley

    0

Please sign in to leave a comment.