Benders decomposition example in Python
AnsweredHi Guys I'm in a hurry. Do you know where could I find benders decomposition examples with Python? any help appreciated.
-
-
Gurobi Staff
Hi Iason,
A Benders decomposition algorithm in Gurobi is basically just a branch-and-cut algorithm where you add Benders cuts in lazy-constraint and/or user-cut callbacks. So you can use any example that shows cut callbacks, e.g., the TSP example. You then need to derive the Benders cuts based on your particular model and the way you want to decompose.
There was already some discussion about Benders in this forum, please search for it.
Best regards,
Mario0 -
-
Thanks Mario, Do you know other examples that use callbacks?
Kind regards
Iason0 -
-
-
What exactly do you have in mind?
The TSP example or this more basic callback example show you how to do it technically. The rest, i.e., which cuts to add and how to identify violated cuts, is specific to your problem. How to derive Benders cuts in general can be found in any textbook or paper on Benders decomposition.
0 -
-
Thanks Mario, I was wondering if there are more examples with callbacks since I see that there are many ways that they can be applied and many functions. But it might not be needed since there are function explanations on the Gurobi site.
Kind regards
Iason0 -
-
Mario, Do you know what does the line
m._vars = varsin the TSP do? It is in the section Solve The Model.
Kind regards0 -
-
for what set of variables do we have to make this definition? the ones that we use in the callback or every set of variables that is used in the model?
Kind regards
Iason0 -
-
-
This is just some way to pass variables or other values to the callback function if you want to use them there, since the callback method just gets the model as parameter.
You could also access your variables and data via global Python variables.
0 -
-
Thanks Mario!
0 -
-
Hi Mario, what do user-cut callbacks mean? Is this just another name for implementing lazy constraint add? is there another way to implement lazy constraint for bender's decomposition?
0 -
-
See this article: What is the difference between user cuts and lazy constraints?
Is there a specific reason why you are asking if there is another way to add lazy constraints? Are you missing something?
0 -
Please sign in to leave a comment.
Comments
10 comments