Skip to main content

Dual values for maximization problem with and without variable upper bound

Answered
Grzegorz Siekaniec
Gurobi-versary
Curious
First Comment

Hello,

I have a maximization model with slightly different, but equivalent, formulations:
1. Variables have bounds.
2. Variables do not have bounds.
3. Variables bounds are expressed as constraints.

Below are formulations.

1. Variables have bounds.

\ Model GAP_variables_with_upper_bound
\ LP format - for model browsing. Use MPS format to capture full model detail.
Maximize
22 machine_0_tasks_0_1_2_5 + 12 machine_1_tasks_3_4_6
Subject To
task_assignment_0: machine_0_tasks_0_1_2_5 = 1
task_assignment_1: machine_0_tasks_0_1_2_5 = 1
task_assignment_2: machine_0_tasks_0_1_2_5 = 1
task_assignment_3: machine_1_tasks_3_4_6 = 1
task_assignment_4: machine_1_tasks_3_4_6 = 1
task_assignment_5: machine_0_tasks_0_1_2_5 = 1
task_assignment_6: machine_1_tasks_3_4_6 = 1
convexity_machine_0: machine_0_tasks_0_1_2_5 = 1
convexity_machine_1: machine_1_tasks_3_4_6 = 1
Bounds
machine_0_tasks_0_1_2_5 <= 1
machine_1_tasks_3_4_6 <= 1
End

2. Variables do not have bounds.

\ Model GAP_variables_with_no_upper_bound
\ LP format - for model browsing. Use MPS format to capture full model detail.
Maximize
22 machine_0_tasks_0_1_2_5 + 12 machine_1_tasks_3_4_6
Subject To
task_assignment_0: machine_0_tasks_0_1_2_5 = 1
task_assignment_1: machine_0_tasks_0_1_2_5 = 1
task_assignment_2: machine_0_tasks_0_1_2_5 = 1
task_assignment_3: machine_1_tasks_3_4_6 = 1
task_assignment_4: machine_1_tasks_3_4_6 = 1
task_assignment_5: machine_0_tasks_0_1_2_5 = 1
task_assignment_6: machine_1_tasks_3_4_6 = 1
convexity_machine_0: machine_0_tasks_0_1_2_5 = 1
convexity_machine_1: machine_1_tasks_3_4_6 = 1
Bounds
End

3. Variables bounds are expressed as constraints.

\ Model GAP_variables_with_upper_bound_as_constraint
\ LP format - for model browsing. Use MPS format to capture full model detail.
Maximize
22 machine_0_tasks_0_1_2_5 + 12 machine_1_tasks_3_4_6
Subject To
task_assignment_0: machine_0_tasks_0_1_2_5 = 1
task_assignment_1: machine_0_tasks_0_1_2_5 = 1
task_assignment_2: machine_0_tasks_0_1_2_5 = 1
task_assignment_3: machine_1_tasks_3_4_6 = 1
task_assignment_4: machine_1_tasks_3_4_6 = 1
task_assignment_5: machine_0_tasks_0_1_2_5 = 1
task_assignment_6: machine_1_tasks_3_4_6 = 1
convexity_machine_0: machine_0_tasks_0_1_2_5 = 1
convexity_machine_1: machine_1_tasks_3_4_6 = 1
Upper_bound_machine_0_tasks_0_1_2_5: machine_0_tasks_0_1_2_5 <= 1
Upper_bound_machine_1_tasks_3_4_6: machine_1_tasks_3_4_6 <= 1
Bounds
End

All formulations have one solution. Below is information about objective value and dual value.

Model >GAP_variables_with_upper_bound< objective value: 34.0
Model >GAP_variables_with_upper_bound< duals: [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0]

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]

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]

Questions

I would like to ask:
1. Why do formulations GAP_variables_with_upper_bound and GAP_variables_with_no_upper_bound have different dual values?
2. Why there is no difference in dual values in case of changing problem to be minimzation problem?

Below is full script used to reproduce problem:

from typing import List, Tuple, Dict

import numpy as np
import gurobipy as grb


num_machines = 2
num_tasks = 7

weights = np.array([
    [4, 1, 2, 1, 4, 3, 8],
    [9, 9, 8, 1, 3, 8, 7]
])

profits = np.array([
    [6, 9, 4, 2, 10, 3, 6],
    [4, 8, 9, 1, 7, 5, 4]
])

capacity = np.array([11, 22])

initial_solution = [
    (0, [0, 1, 2, 5]),
    (1, [3, 4, 6])
]


def machine_schedule_profit(machine_schedule) -> float:
    machine_id = machine_schedule[0]
    tasks = machine_schedule[1]
    return profits[machine_id][tasks].sum()


def build_task_constraints(model) -> Dict:
    task_to_constraint = dict()
    for task_id in range(num_tasks):
        lhs = grb.quicksum([])
        rhs = 1
        name = f'task_assignment_{task_id}'
        c = model.addConstr(lhs == rhs, name=name)
        task_to_constraint[task_id] = c
    return task_to_constraint


def build_convexity_constraints(model) -> Dict:
    machine_to_constraint = dict()
    for machine_id in range(num_machines):
        lhs = grb.quicksum([])
        rhs = 1
        name = f'convexity_machine_{machine_id}'
        c = model.addConstr(lhs == rhs, name=name)
        machine_to_constraint[machine_id] = c
    return machine_to_constraint


def get_column(machine_schedule, machine_to_constraint, task_to_constraint) -> grb.Column:
    machine_id = machine_schedule[0]
    tasks = machine_schedule[1]

    c = grb.Column()
    coeff = 1.0
    for task in tasks:
        constr = task_to_constraint[task]
        c.addTerms(coeff, constr)

    machine_constr = machine_to_constraint[machine_id]
    c.addTerms(coeff, machine_constr)
    return c


def model_1():
    model = grb.Model("GAP_variables_with_upper_bound")
    model.setAttr(grb.GRB.Attr.ModelSense, grb.GRB.MAXIMIZE)
    model.Params.LogToConsole = 0
    task_to_constraint = build_task_constraints(model)
    machine_to_constraint = build_convexity_constraints(model)

    for machine_schedule in initial_solution:
        machine_id = machine_schedule[0]
        tasks = machine_schedule[1]
        profit = machine_schedule_profit(machine_schedule)

        name = f"machine_{machine_id}_tasks_{'_'.join(str(task_id) for task_id in tasks)}"
        column = get_column(machine_schedule, machine_to_constraint, task_to_constraint)

        _var = model.addVar(
            lb=0.0,
            ub=1.0,
            obj=profit,
            vtype=grb.GRB.CONTINUOUS,
            name=name,
            column=column
        )

    model.update()
    model.write(model.ModelName + '.lp')
    model.optimize()
    print(f"Model >{model.ModelName}< objective value: {model.ObjVal}")
    print(f"Model >{model.ModelName}< duals: {model.Pi}")


def model_2():
    model = grb.Model("GAP_variables_with_no_upper_bound")
    model.setAttr(grb.GRB.Attr.ModelSense, grb.GRB.MAXIMIZE)
    model.Params.LogToConsole = 0
    task_to_constraint = build_task_constraints(model)
    machine_to_constraint = build_convexity_constraints(model)

    for machine_schedule in initial_solution:
        machine_id = machine_schedule[0]
        tasks = machine_schedule[1]
        profit = machine_schedule_profit(machine_schedule)

        name = f"machine_{machine_id}_tasks_{'_'.join(str(task_id) for task_id in tasks)}"
        column = get_column(machine_schedule, machine_to_constraint, task_to_constraint)

        _var = model.addVar(
            lb=0.0,
            # ub=1.0,
            obj=profit,
            vtype=grb.GRB.CONTINUOUS,
            name=name,
            column=column
        )

    model.update()
    model.write(model.ModelName + '.lp')
    model.optimize()
    print(f"Model >{model.ModelName}< objective value: {model.ObjVal}")
    print(f"Model >{model.ModelName}< duals: {model.Pi}")


def model_3():
    model = grb.Model("GAP_variables_with_upper_bound_as_constraint")
    model.setAttr(grb.GRB.Attr.ModelSense, grb.GRB.MAXIMIZE)
    model.Params.LogToConsole = 0
    task_to_constraint = build_task_constraints(model)
    machine_to_constraint = build_convexity_constraints(model)

    for machine_schedule in initial_solution:
        machine_id = machine_schedule[0]
        tasks = machine_schedule[1]
        profit = machine_schedule_profit(machine_schedule)

        name = f"machine_{machine_id}_tasks_{'_'.join(str(task_id) for task_id in tasks)}"
        column = get_column(machine_schedule, machine_to_constraint, task_to_constraint)

        var = model.addVar(
            lb=0.0,
            # ub=1.0,
            obj=profit,
            vtype=grb.GRB.CONTINUOUS,
            name=name,
            column=column
        )

        _c = model.addConstr(var <= 1.0, name=f'Upper_bound_{name}')

    model.update()
    model.write(model.ModelName + '.lp')
    model.optimize()
    print(f"Model >{model.ModelName}< objective value: {model.ObjVal}")
    print(f"Model >{model.ModelName}< duals: {model.Pi}")

model_1()
model_2()
model_3()
0

Comments

3 comments

Date Votes
  • 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.

Didn't find what you were looking for?

New post