Column generation when number of rows depend on number of columns
AnsweredHi!
I'm trying to solve a MIP with gurobi using column generation. The novel thing (for me) about this problem, is that the set of rows in the problem depends on the set of columns. That is, whenever I add a new column to the restricted master problem, there are N new constraints that must be added as well. My question is how to formulate the pricing problem since the duals of these new constraints does not yet exist in the restricted master problem.
I've described the problem in more detail here https://math.stackexchange.com/questions/4794418/column-generation-when-number-of-rows-depend-on-number-of-columns , because this looks like a generic MIP/LP question not gurobi specific. Perhaps someone on this mailing list knows the answer?
Thanks!
Marco
-
-
Gurobi Staff
Hi Marco,
For me, this sounds like it requires both dynamic column and cut generation, resulting in a branch-price-and-cut algorithm.
Usually, you start with the pricing loop in which you iteratively add all columns with negative reduced costs (in case of minimization) until you can prove that no further such columns exist. In those pricing problems, you only consider the duals for the constraints that currently exist in the model.
Then, you switch to the cut loop, where you iteratively add all violated constraints until you prove that there are no further such constraints by solving the separating problem. In your case, the separation algorithm just might be enumerating the missing constraints for the current variable set.
Then, you have to return to the pricing loop, etc. You switch between the two loops until you cannot find more columns and cuts to add. Then, you have solved the LP relaxation at the current branch-and-bound node.
Best regards,
Mario0 -
-
Hi Mario! Thanks for the answer, that makes sense!
0 -
Please sign in to leave a comment.
Comments
2 comments