Column generation dual variables
AnsweredHi all,
I am trying to solve a minimum cost multi commodity flow problem via a column generation approach.
I formulated the reduced master problem (RMP) as explained here on page 5 (3.1.1/3.1.2).
To initiate the column generation, I add a dummy variable for every trip to the model, in which the Y in constraint (14) is the 0-Matrix and the N in constraint (15) is the unit matrix and the lower bound for the dummy variable is 0.
The cost for every dummy variable in the objective function is M.
This means that after solving the RMP once, every dummy variable has value 1 and the objective value is Mx#flows. The dual variables of the convexity constraints are M for every constraint.
I then solve the pricing problem (page 6, 3.1.3) for every flow and add the new flows with their corresponding variable to the RMP.
My problem arises, when solving the RMP once more.
Since I started by defining high capacities, every found flow can be used without breaking the capacity constraint (14).
All dummy variables now have value 0 and all newly added flow variables have value 1. I expect the dual variables of the convexity constraints (15) for flow k to be the cost of the newly added flow k.
This is the case in around 2/3 of the flows. In the other cases the dual variable stays M.
In all cases where the dual variable stays M, the corresponding dummy variable is in the basis (VBasis = 0).
In all cases where the dual variable is the cost of the newly found flow, the corresponding dummy variable is not in the basis (VBasis = -1)
My two questions are:
Why are not all dual variables of the convexity constraints equal to the cost of the newly found corresponding flows?
Why are some dummy variables in the basis and some not?
Thanks a lot!
UPDATE:
When setting the parameter 'Method' to 0 (primal simplex) the dual variables of the convexity constraints all stay M.
When setting the parameter 'Method' to 1 (dual simplex) the behaviour from above occurs. How can there be different dual variables? Is this an internal Gurobi problem?
-
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?. -
-
It seems that calling RMP.reset() before resolving the RMP again solves this problem.
But I still don't understand why the solver behaves like that.It seems like not knowing this makes Gurobi unusable for column generation, which is a big drawback in my opinion.
0 -
Post is closed for comments.
Comments
2 comments