Skip to main content

Shadow Prices (Pi) in FixedModel Are Incorrectly Zero

Answered
YU-TING HUNG
  • Edited
First Comment
First Question

I used the FixedModel approach to relax the original subproblems and retrieve the dual variables. However, the dual variables, or shadow prices (Pi), are consistently showing as zero, which seems incorrect. How can I resolve this issue to correctly obtain the shadow prices? 

example: 

static void Main(string[] args)
    {
        GRBEnv env = new GRBEnv();
        GRBModel model = new GRBModel(env);      
        GRBVar x = model.AddVar(0.0, GRB.INFINITY, 0.0, GRB.BINARY, "x");
        GRBVar y = model.AddVar(0.0, GRB.INFINITY, 0.0, GRB.BINARY, "y");
        GRBLinExpr expr1 = new GRBLinExpr();
        expr1.AddTerm(1.0, x);
        expr1.AddTerm(1.0, y);
        model.AddConstr(expr1, GRB.LESS_EQUAL, 10.0, "constr1");
        GRBLinExpr objExpr = new GRBLinExpr();
        objExpr.AddTerm(2.0, x);
        objExpr.AddTerm(3.0, y);
        model.SetObjective(objExpr, GRB.MAXIMIZE);
        model.Optimize();
        GRBModel fixedmodel = model.FixedModel();
        fixedmodel.GetEnv().Set(GRB.IntParam.Presolve, 0);
        fixedmodel.Parameters.Presolve = 0;
        fixedmodel.Optimize();
        Console.WriteLine("Dual values:");
        foreach (GRBConstr constr in fixedmodel.GetConstrs())
        {
            //Console.WriteLine($"Constraint {constr.ConstrName}: {constr.Get(GRB.DoubleAttr.Slack)}");
            Console.WriteLine($"Constraint {constr.ConstrName}: {constr.Get(GRB.DoubleAttr.Pi)}");
        }

Related to

0

Comments

3 comments

Date Votes
  • Gurobot AI-generated response
    Gurobi Staff Gurobi Staff

    When you are using Gurobi's FixedModel approach to relax original subproblems and retrieve dual variables (or shadow prices), it is crucial to set up the model correctly to ensure that these dual values are meaningful and correctly computed. If the dual variables are consistently showing as zero, it may be due to several reasons:

    1. Constraint Activity: Dual variables (shadow prices) will be zero for constraints that are not active (binding) at the optimal solution. An active (or binding) constraint is one where the constraint equation holds as an equality at the optimal solution.

    2. Model Type and Variable Types: Since you're dealing with binary variables (as seen from the model creation where variables x and y are defined as binary), the concept of dual variables becomes tricky. Binary variables inherently turn the problem into a combinatorial optimization problem, where linear programming duality (which gives rise to dual variables) may not straightforwardly apply.

    3. Presolve and Relaxation: Your use of FixedModel along with disabling presolve (fixedmodel.Parameters.Presolve = 0) is correct for obtaining a model that allows you to retrieve dual values directly. However, ensure that the constraints are indeed binding, and consider if the model needs relaxation (e.g., changing binary variables to continuous if applicable) to make sense of dual values in a linear or mixed-integer context.

    Steps to Resolve the Issue:

    • Check Constraint Activity: Ensure that the constraints are active. You can check this by looking at the slack of each constraint. If the slack is not zero, the constraint is not active, and the dual value will typically be zero.

    • Relax Binary Variables: If appropriate for your analysis, consider relaxing the binary constraints on the variables to continuous variables (e.g., 0 to 1 instead of strictly 0 or 1). This can provide a linear programming relaxation that allows more meaningful interpretation of shadow prices: 
      x = model.AddVar(0.0, 1.0, 0.0, GRB.CONTINUOUS, "x");
      y = model.AddVar(0.0, 1.0, 0.0, GRB.CONTINUOUS, "y");
    • Model Recalculation: After making any changes such as the above relaxation, rerun the optimization and then fix the model again to check the duals: 
      model.Optimize();
      GRBModel fixedmodel = model.FixedModel();
      fixedmodel.GetEnv().Set(GRB.IntParam.Presolve, 0);
      fixedmodel.Optimize();

    • Interpret Results Carefully: When interpreting results from a relaxed model, remember that relaxing binary constraints changes the nature of the solution space and may impact the applicability of the results to your original binary model.

    • Debugging and Validation: Validate the output by checking whether constraints are active and by considering different scenarios or parameter values to see how they affect the dual values.


      Here's an example of how you might adjust your code to check for active constraints and consider relaxation:
      foreach (GRBConstr constr in fixedmodel.GetConstrs())
      {
          double slack = constr.Get(GRB.DoubleAttr.Slack);
          double pi = constr.Get(GRB.DoubleAttr.Pi);
          Console.WriteLine($"Constraint {constr.ConstrName}: Slack={slack}, Pi={pi}");
      }

      This output will give you a better insight into which constraints are actively shaping the solution and their corresponding shadow prices. If relaxing the model or other changes are not appropriate, further investigation into model formulation or consultation with optimization experts might be necessary.

    0
  • YU-TING HUNG
    First Comment
    First Question 
    When I use the fixedModel(), can't I get the Shadow Prices (Pi)?
    0
  • Matthias Miltenberger
    Gurobi Staff Gurobi Staff

    Yes, you should be able to get the dual values of a MIP problem using the fixedModel approach: How do I retrieve the (dual) Pi values for a MIP problem? – Gurobi Help Center

    0

Please sign in to leave a comment.

Didn't find what you were looking for?

New post