Multiple subproblems
Answered
Hi,
Just a generic question: how to program multiple subproblems in Gurobi C++? Is this possible without hard coding each and every subproblem?
-
Hi Elisabeth,
It is hard to answer this question in general without having more specific information.
What exactly do you mean by subproblems: subproblems in the sense of Column Generation or Benders Decomposition? Or in some other sense?
As a general answer, there is no specific framework that the Gurobi C++ API provides to automatize this. But for example, if the different subproblems have the same structure (same constraints -- disregarding coefficients) and only the data (matrix coefficients, objective coefficients, right-hand-sides) changes, then you can automatize the task by storing the coefficients in files and read them in with a function to construct the subproblems.
Elisabeth
0 -
Hi Elisabeth,
Subproblems in the sense of Column Generation. The subproblems indeed have the same structure, the only way in which they differ is by the number of decision variables (so it's one constant that needs to be changed when making the decision variables). Do I have to make different Gurobi models for each subproblem or do I have to overwrite the model? Do I have to loop over the different subproblems?
Thanks for your support.
0 -
Hi Elisabeth,
If the number of decision variables changes then it is not only a constant that has to be changed, since this means that there will be some variables that are present in some of the subproblems and not in others. (Although you can also interpret this as a data change: these variables will have a coefficient of 0 in some of the subproblems.)
I found a Column Generation implementation in C++ of the Cutting Stock problem in our old Google Group: https://groups.google.com/g/gurobi/c/pkBNfu-iX0k. I haven't checked it in detail, but it might be helpful to help you get started. As you can see, the pricing problems are created in a loop. At each iteration, a GRBModel object is created to store the pricing problem. This is also the approach that I would recommend. The post is a little old, so maybe some of the syntax has changed.
Please note that Gurobi does not support branch-and-price, so you cannot solve a MIP to optimality by adding variables with negative reduced costs on the fly. But you can solve the LP relaxation of your model with column generation. For more information, please have a look at this very informative post.
I hope this helps.
Elisabeth
0
Please sign in to leave a comment.
Comments
3 comments