Decision Optimization

Expand all | Collapse all

Incorrect shadow price values in CPLEX

  • 1.  Incorrect shadow price values in CPLEX

    Posted Tue November 17, 2020 03:51 AM
      |   view attached
    Hi everyone, 
    I am trying to retrieve the shadow price values of some constraints in a CPLEX based optimization problem, but it seems the values are incorrect. 

    Problem statement:
    (Please also see the model formulation in the attached .mod file.)

    Constraints:
    (1) A demand product can be fulfilled by either of 2 alternative inputs AO and BO.
    (2) To produce AO (BO), we need both AI (BI) and MAT at the same time.
    (3) AO and BO are flow parts, which should always have 0 end on hand inventory (EOH).
    (4) All parts have inventory costs.

    Objectives: minimize backorder cost + inventory cost.

    Data:
    (1) Inventory cost: Demand = 20, AO = BO = 10000, AI = BI = 10, MAT = 5.
    (2) Demand quantity = 100, priority = 30.
    (3) Beginning on hand inventory (BOH): AI = 200, MAT = 150.

    Solving results:
    (1) backorder quantity = 0. Inventory cost = 3250.
    (2) Shadow price:
    the shadow price value of AI = 10
    the shadow price value of BI = -5

    Question:
    Why the shadow price values of AI and BI are different? Because of the constraint (1) and (2) and equal inventory cost, we think AI and BI are alternative. It is difficult for me to explain why AI and BI have different shadow price values. Can anyone help? 

    Thank you very much. 


    ------------------------------
    Best Regards,
    Hui Zhao
    ------------------------------

    Attachment(s)

    mod
    atpmp_simple.mod   3 KB 1 version


  • 2.  RE: Incorrect shadow price values in CPLEX

    Posted Tue November 17, 2020 09:15 AM
    Hi,

    if you rewrite your constraint into

    forall (n in Node_List) {
    EOH_Constraint1:
    EOH[n] <= BOHQty[n] +
    sum (out in Output_Node_List: out == n)loadingOutput[out]
    - sum (p1 in Non_Alternative_Production: p1.Input == n)loadingInput[p1.Output][n]
    - sum (p2 in Alternative_Production: p2.Input == n)loadingInput[p2.Output][n];

    EOH_Constraint2:
    BOHQty[n] +
    sum (out in Output_Node_List: out == n)loadingOutput[out]
    - sum (p1 in Non_Alternative_Production: p1.Input == n)loadingInput[p1.Output][n]
    - sum (p2 in Alternative_Production: p2.Input == n)loadingInput[p2.Output][n] <=EOH[n];

    }

    Then you ll get

    the shadow price value of AO = 0
    the shadow price value of AO = -15
    the shadow price value of BO = 0
    the shadow price value of BO = 0
    the shadow price value of DEMAND = 0
    the shadow price value of DEMAND = -20
    the shadow price value of MAT = 0
    the shadow price value of MAT = -5
    the shadow price value of AI = 0
    the shadow price value of AI = -10
    the shadow price value of BI = -5
    the shadow price value of BI = 0

    An equality is a set of <= and >=

    regards

    ------------------------------
    [Alex] [Fleischer]
    [EMEA CPLEX Optimization Technical Sales]
    [IBM]
    ------------------------------



  • 3.  RE: Incorrect shadow price values in CPLEX

    Posted Wed November 18, 2020 12:57 AM
    Hi Alex,
    Thank you so much for your instant reply.

    I can understand your saying "An equality is a set of <= and >=", but I still have some questions:
    (1) Why we need such a transformation? 
    (2) No matter before or after transformation, the shadow price values of AI and BI are different. Why? Since they are actually alternative to the Demand and have the same cost structure, I think they should have the same shadow price value. 
    In detail, we have the following results in the original case. We can try to explain from the concept of shadow price. 
    1. the shadow price value of AI = 10. (This can be explained by AI's inventory cost. Adding one unit of AI can increase the objective function value by 10 (AI's inventory cost.)
    2. the shadow price value of BI = -5. (I guess the value -5 comes from the reduction of one unit of MAT (MAT's inventory cost is -5. But this will violate the constraint (3) AO and BO are flow parts, which should always have 0 end on hand inventory (EOH).)

    Can you help to further explain?
    Thank you very much. 


    ------------------------------
    Hui Zhao
    ------------------------------



  • 4.  RE: Incorrect shadow price values in CPLEX

    Posted Wed November 18, 2020 04:01 AM
    Hi,

    let s keep only

    forall (n in Node_List) {


    EOH_Constraint:
    BOHQty[n] +
    sum (out in Output_Node_List: out == n)loadingOutput[out]
    - sum (p1 in Non_Alternative_Production: p1.Input == n)loadingInput[p1.Output][n]
    - sum (p2 in Alternative_Production: p2.Input == n)loadingInput[p2.Output][n] <=
    EOH[n];

    }

    then you get

    // solution (optimal) with objective 3250
    the shadow price value of AO = -15
    the shadow price value of BO = -5
    the shadow price value of DEMAND = -20
    the shadow price value of MAT = -5
    the shadow price value of AI = -10
    the shadow price value of BI = 0

    which you can check:

    if you write

    EOH_Constraint:
    BOHQty[n] +
    sum (out in Output_Node_List: out == n)loadingOutput[out]
    - sum (p1 in Non_Alternative_Production: p1.Input == n)loadingInput[p1.Output][n]
    - sum (p2 in Alternative_Production: p2.Input == n)loadingInput[p2.Output][n] <=
    EOH[n]+(n=="AI");

    you get objective 3240 which is inline with dual cost 10 for AI

    whereas if you write

    EOH_Constraint:
    BOHQty[n] +
    sum (out in Output_Node_List: out == n)loadingOutput[out]
    - sum (p1 in Non_Alternative_Production: p1.Input == n)loadingInput[p1.Output][n]
    - sum (p2 in Alternative_Production: p2.Input == n)loadingInput[p2.Output][n] <=
    EOH[n]+(n=="BI");

    then you still get 3250 which is inline with dual cost 0 for BI

    regards






    ------------------------------
    [Alex] [Fleischer]
    [EMEA CPLEX Optimization Technical Sales]
    [IBM]
    ------------------------------



  • 5.  RE: Incorrect shadow price values in CPLEX

    Posted Wed November 18, 2020 04:31 AM
    Hi Alex,
    Thanks for your fast reply. 
    I understand what you explained. 
    My question is: the concept of shadow price is violated here in my original problem where the EOH constraint is an equation. 

    (1) The shadow price value in the original problem.
    // solution (optimal) with objective 3250
    the shadow price value of AO = 15
    the shadow price value of BO = 0
    the shadow price value of DEMAND = 20
    the shadow price value of MAT = 5
    the shadow price value of AI = 10
    the shadow price value of BI = -5

    (2) When I change BOH as below, the solution is changed from 3250 to 3260. It means the shadow price value of AI is correct. 
    Before: BOH = {<"AI", 200>, <"MAT", 150>}
    After: BOH = {<"AI", 201>, <"MAT", 150>}
    // solution (optimal) with objective 3260

    (3) However, when I change BOH where BI is added in BOH, the solution is changed from 3250 to 3260 too, but not 3245 based on the shadow price value (-5) in the original problem. Meanwhile, the shadow price value of BI becomes 10, which is the correct one.
    With this observation, I am guessing if CPLEX removes the constraints for BI in preprocess and results in the wrong shadow price value of BI
    Before: BOH = {<"AI", 200>, <"MAT", 150>}
    After: BOH = {<"AI", 200>, <"BI", 1>, <"MAT", 150>}

    // solution (optimal) with objective 3260
    the shadow price value of AO = 15
    the shadow price value of BO = 15
    the shadow price value of DEMAND = 20
    the shadow price value of MAT = 5
    the shadow price value of AI = 10
    the shadow price value of BI = 10

    Looking forward to your reply soon.


    ------------------------------
    Hui Zhao
    ------------------------------