Dual variables are not updated in column generation with Farkas cost
AnsweredHi All,
We are trying to implement a column generation algorithm where we deal with infeasible problems with Farkas cost. In the following python example we run into the problem that the dual variables do not update from the first to the second iteration. Doing a reset() fixes this problem, but we would ideally like to maintain warm starts. Is there a way of doing this?
Thanks in advance!
from gurobipy import *
rmp = Model("RMP")
# We set this so we can get the dual ray for Farkas cost
rmp.setParam("InfUnbdInfo", True)
# Set up initial variable
p_1 = rmp.addVar(name="p_1", lb=0, ub=1, obj=3)
rmp.update()
# Set up initial constraints
rmp.addConstr(p_1 == 1, "convexity")
rmp.addConstr(0.5 * p_1 == 0, "regroup_a")
rmp.update()
# Optimise the LP -- we know it will be infeasible
rv = rmp.optimize()
# Since the LP is infeasible, we get the dual rays to compute the Farkas cost
dual_ray_conv = rmp.getConstrByName("convexity").getAttr("FarkasDual")
dual_ray_rgrp_a = rmp.getConstrByName("regroup_a").getAttr("FarkasDual")
# We find the column with minimal Farkas cost by hand, using the dual rays
# Add the new column to our LP
# (This column is a "cycle" and is therefore left out of the objective)
column_c_1 = Column()
column_c_1.addTerms(-0.5, rmp.getConstrByName("regroup_a"))
rmp.addVar(name="c_1", lb=0, ub=GRB.INFINITY, obj=4, column=column_c_1)
rmp.update()
# Optimise the LP -- it will be feasible. We treat this as the first iteration
# of column generation.
rmp.optimize()
# Value of the dual variables for the RMP (mu^*) in the first iteration.
mu_1_conv = rmp.getConstrByName("convexity").getAttr("Pi")
mu_1_rgrp_a = rmp.getConstrByName("regroup_a").getAttr("Pi")
# We find the column with minimal cost in the pricing problem by hand,
# using the dual variables
# Add the new column to our LP
# (This column is a "plan" and is therefore included in the objective)
column_p_2 = Column()
column_p_2.addTerms(1.0, rmp.getConstrByName("convexity"))
rmp.addVar(name="p_2", lb=0, ub=1, obj=5, column=column_p_2)
rmp.update()
########################################################################
########################################################################
rmp.reset() # throwing out the warm start gives us the correct answer!
########################################################################
########################################################################
# The LP will be feasible and optimal at this stage, so the pricing
# problem will return 0
rmp.optimize()
# Getting the dual variables.
mu_2_conv = rmp.getConstrByName("convexity").getAttr("Pi")
mu_2_rgrp_a = rmp.getConstrByName("regroup_a").getAttr("Pi")
# The values should be 5 and -8 respectively but we are getting 7 and -8 -- ie. the old dual vars
print("\n\n-------------------------\n\n")
print("Dual vars. from previous iteration: {}, {}".format(mu_1_conv, mu_1_rgrp_a))
print("Dual vars. from current iteration: {}, {}".format(mu_2_conv, mu_2_rgrp_a))
print("Expected dual vars. for current iteration: 5.0, -8.0")
-
Official comment
-
Gurobi Staff
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?. -
-
-
I suspect this is due to the upper bounds on the \( p \) variables. Because these variables have finite upper bounds of \( 1 \), their reduced costs can be negative, which your algorithm may not expect. There's a nice post discussing this here.
Because the \( p \) variables are nonnegative, the convexity constraint \( \sum_{i = 1}^n p_i = 1 \) implies that each \( p \) variable is no greater than \( 1 \). So, I suspect you can resolve this issue by removing the upper bounds on the \( p \) variables.
0 -
-
Thanks! The post you linked explains the problem, and your solution indeed seems to work.
0 -
Post is closed for comments.
Comments
3 comments