Skip to main content

Dual values for maximization problem with and without variable upper bound

Answered

Comments

3 comments

  • Maliheh Aramon
    Gurobi Staff Gurobi Staff

    Hi Grzegorz,

    As you already know, we can think of dual variables as a vector of shadow prices for the right-hand-side vector of the primal problem. In your example, the \(i\)-th constraint represents the capacity of one for machine \(i\) and the objective function represents the profit of scheduling tasks. The dual variable for constraint \(i\) is then the incremental profit as a result of increasing the capacity of machine \(i\) by one unit. 

    The dual variables associated with variable bounds can be queried using the RC (reduced cost) attribute . 

    for var in model.getVars():
    print(f"Var >{var.VarName}< duals: {var.RC}")

    You will see:

    model_1
    Var >machine_0_tasks_0_1_2_5< duals: 22.0

    Var >machine_1_tasks_3_4_6< duals: 12.0

    model_2
    Var >machine_0_tasks_0_1_2_5< duals: 0.0
    Var >machine_1_tasks_3_4_6< duals: 0.0

    model_3
    Var >machine_0_tasks_0_1_2_5< duals: 0.0
    Var >machine_1_tasks_3_4_6< duals: 0.0

    Regarding your second question, changing the model sense to minimization gives you:

    model_1
    Model >GAP_variables_with_upper_bound< objective value: 34.0

    Model >GAP_variables_with_upper_bound< duals: [22.0, 0.0, 0.0, 12.0, 0.0, 0.0, 0.0, 0.0, 0.0]
    Var >machine_0_tasks_0_1_2_5< duals: 0.0
    Var >machine_1_tasks_3_4_6< duals: 0.0

    model_2
    Model >GAP_variables_with_no_upper_bound< objective value: 34.0
    Model >GAP_variables_with_no_upper_bound< duals: [22.0, 0.0, 0.0, 12.0, 0.0, 0.0, 0.0, 0.0, 0.0]
    Var >machine_0_tasks_0_1_2_5< duals: 0.0
    Var >machine_1_tasks_3_4_6< duals: 0.0

    model_3
    Model >GAP_variables_with_upper_bound_as_constraint< objective value: 34.0
    Model >GAP_variables_with_upper_bound_as_constraint< duals: [22.0, 0.0, 0.0, 12.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0]
    Var >machine_0_tasks_0_1_2_5< duals: 0.0
    Var >machine_1_tasks_3_4_6< duals: 0.0

    The dual values do not change because all your three models contain only one solution point where the minimum and maximum happen at the same solution point. 

    Looking at this from a high-level perspective, the way you have defined your models is not super clear to me. From the code snippet, your problem is a knapsack-type problem. The primal (dual) problem is to maximize profit subject to capacity constraints and the dual (primal) problem is to minimize the capacity subject to constraints that the capacity used per task is not lower than its profit. 

    However, your models are defined as a fixed-point model using an initial solution. Could please explain how you are planning to use these dual values?

    Best regards,

    Maliheh

    0
  • Grzegorz Siekaniec
    Gurobi-versary
    Curious
    First Comment

    Hi Maliheh,

    thanks for prompt answer. I stumbled across this one in the context of column generation and initial solution. The example that I provided here was the smallest one where I managed to reproduce issue that I was facing.

    Thanks for pointing out possibility of retrieving reduced cost from variable, I was not aware of it. But then, I have a follow up question as, I would expect that "model.Pi" give me the same set of dual values for both model_1 and model_3. In my understanding, setting bounds for variable during its creation is just convenience. And whether I do this or set bounds as constraints, I kind of expect the same set of dual values. But maybe it is not the case, then I am curious to know what are the reasons.

    Appreciate your help on this one.

    0
  • Maliheh Aramon
    Gurobi Staff Gurobi Staff

    Hi Grzegorz,

    Variable bounds are not a convenience feature for adding simple model constraints. Internally, Gurobi treats variable bounds differently than constraints.

    An optimization problem can have multiple optimal solutions. Gurobi only reports one by default that can also change using different parameter settings.

    To make it more clear, let us write the dual of model_1 and model_3 after removing the redundant constraints. Further, let us assume \(x_1\) and \(x_2\) represent \(\texttt{machine_0_tasks_0_1_2_5}\) and \(\texttt{machine_1_tasks_3_4_6}\), respectively.

    model_1: Primal (bounds are not constraints and are not removed)

    \[\begin{align} \max ~ & 22x_1 + 12x_2 & \notag \\ \mbox{s.t.} ~ & x_1 = 1 & \notag \\ & x_2 = 1 & \notag \\ & 0 \leq x_1, x_2 \leq 1 & \end{align}\]

    model_1: Dual 

    • \(y_1\) and \(y_2\) are the duals corresponding to the constraints \(x_1=1\) and \(x_2=1\), respectively.
    • \(y_3\) and \(y_4\) are the duals corresponding to the variable bounds \(x_1 \leq 1 \) and \(x_2 \leq 1\), respectively.

    \[\begin{align} \min ~ & y_1 + y_2 + y_3 + y_4 & \notag \\ \mbox{s.t.} ~ & y_1 + y_3 \geq 22 & \notag \\ & y_2 + y_4 \geq 12 & \notag \\ & y_1, y_2 ~ \text{free} & \notag \\ & y_3, y_4 \geq 0 & \notag \end{align}\]

    The dual of model_1 has many degenerate optimal solutions. Both \([22, 12, 0, 0]\) and \([0, 0, 22, 12]\) are valid solutions.

    model_3: Primal (\(x_1 \leq 1\) and \(x_2 \leq 1\) constraints are removed because they are redundant)

    \[\begin{align} \max ~ & 22x_1 + 12x_2 & \notag \\ \mbox{s.t.} ~ & x_1 = 1 & \notag \\ & x_2 = 1 & \notag \\ & x_1, x_2 \geq 0 & \end{align}\]

    model_3: Dual 

    • \(y_1\) and \(y_2\) are the duals corresponding to the constraints \(x_1=1\) and \(x_2=1\), respectively.

    \[\begin{align} \min ~ & y_1 + y_2 & \notag \\ \mbox{s.t.} ~ & y_1  \geq 22 & \notag \\ & y_2 \geq 12 & \notag \\ & y_1, y_2 ~ \text{free} & \notag \end{align}\]

    The dual of model_3 has the optimal solution of \([22, 12]\).  

    I am not still sure how and why you are using an initial solution in the context of column generation. Since there is a knapsack problem in your application, you might be looking at the column generation for cutting stock problem. Looking at these lecture notes might help you to better address the issue you are facing.

    Best regards,

    Maliheh

    0

Please sign in to leave a comment.

Powered by Zendesk