Why are the dual prices different for the same Gurobi LP model?

回答済み

S J

2019年10月24日 17:35

• 
• 
• 

Environment: Gurobi 8.1.1 + python3

I tried to build the following linear program model and print the dual price.

min 100 x + y

s.t. x + y >= 1 && 0 <= x, y <= 1

Following is the code:

from gurobipy import *

m = Model()

x = m.addVar(name='X', vtype=GRB.CONTINUOUS, ub=1, lb=0, obj=0)
y = m.addVar(name='Y', vtype=GRB.CONTINUOUS, ub=1, lb=0, obj=0) # first x then y

m.setObjective( x + 100 * y , sense=GRB.MINIMIZE  )

m.addConstr( x + y >= 1 )

m.optimize()

print(m.getAttr('Pi', m.getConstrs()))

The output is 1.

But when the two variables are defined in different order, see the following code, the output is 100.

from gurobipy import *

m = Model()

y = m.addVar(name='Y', vtype=GRB.CONTINUOUS, ub=1, lb=0, obj=0)
x = m.addVar(name='X', vtype=GRB.CONTINUOUS, ub=1, lb=0, obj=0) # first y then x

m.setObjective( x + 100 * y , sense=GRB.MINIMIZE  )

m.addConstr( x + y >= 1 )

m.optimize()

print(m.getAttr('Pi', m.getConstrs()))

Why are they different?

0

• 正式なコメント

  

  Simranjit Kaur

  • Gurobi Staff

  2024年12月06日 00:52

  This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?.
• 

  Eli Towle

  • Gurobi Staff

  2019年10月24日 18:23

  Hi SJ,

  This is the result of degeneracy (caused by the upper bounds of x and y). While these two programs produce the same feasible solution, the optimal bases are different for each of the solutions. You can verify this by checking the VBasis variable attributes and CBasis constraint attributes. Shadow prices can differ for different bases corresponding to the same feasible solution.

  Does this help? Thanks!

  Eli

  1
• 

  S J

  2019年10月25日 07:51

  • 
  • 
  • 

  @Eli Towle

  Hi Eli, thanks for your answer.

   

  Still have a very beginner question...

  In dual program, [100] does not seem to be feasible.  Is [100] a *correct* shadow price of optimal solution?

  0
• 

  Thomas Opfer

  2019年10月25日 15:58

  • 
  • 

  Let's w.l.o.g. rewrite your problem to the following standard form:

  min 100 x + y
  s.t.
  x + y >= 1
  - x >= - 1
  - y >= - 1
  x, y >= 0

  Then the dual problem is:

  max d1 - d2 - d3
  s.t.
  d1 - d2 <= 100
  d1 - d3 <= 1
  d1, d2, d3 >= 0

  For this dual, ( d1 = 1, d2 = 0, d3 = 0 ) and ( d1 = 100, d2 = 0, d3 = 99 ) produce the same optimal value (= 1).

  Of course, one could define the signs in the dual a little different, but the result is the same.

  So 100 is a perfectly correct shadow price for the constaint x + y >= 1.

  Best regards,
  Thomas

  2

投稿コメントは受け付けていません。