Implementation of Benders Decomposition with Callbacks
Answered
Hi,
I am trying to implement Benders Decomposition for a minimization problem with Callback lazy optimality cuts (because my sub-problem is always feasible for any feasible master variables). First, I prepare a master problem model (including only master problem variables). Then, I solve the master model and during "where == GRB.Callback.MIPSOL", I check the objective value at that node to get the LB and then solve a sub-problem to get the UB. If UB - LB > tol, then I apply some lazy optimality cuts to the model. The model works but it converges to a wrong optimal solution with objective value far less than the optimal objective value. It seems that initial cuts are weak and the UB goes lower than the optimal value. One way to avoid this problem is to restart the callback with external optimal cut applied. However, this implementation is slower than the straightforward implementation of Benders Decomposition. Is there a way to tell the solver to not have an optimal value less than a specific value?
Thanks,
-
Official comment
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?. -
Hi Pramesh,
You could add a constraint which forces the objective to be above some specific value. This may however negatively affect the performance as described in the Knowledge Base article How do I pass an objective bound to Gurobi?
Best regards,
Jaromił0 -
Hi, I have the same question:
if where == GRB.Callback.MIPSOL:
### Retrieve the cuurent value of the master problem
r_1 = np.array(
[[model.cbGetSolution(model.getVarByName('r_' + str(i) + str(j))) for j in range(N + 1)] for i in
range(N + 1)])
z_1 = np.array(
[[[model.cbGetSolution(model.getVarByName('z_' + str(i) + str(j) + str(l))) for l in range(L)] for j in
range(N + 1)]
for i in range(N + 1)])
### Retrieve the current valur of master problem as the lower bound
LB = model.cbGet(GRB.Callback.MIPSOL_OBJ)
### Solve the dual variable with the cuurent z_1 and return the dual problem's status and value
status, value_list, UB = self.sub_problem(z_1)if status == 2:
### add optimality cut
### When the UB and LB are not equal, add the optimality cut
if abs(UB - LB) >= 0.01:
model.cbLazy(model.getVarByName('q') >= lin)
#### model.write('test.lp')
else:
### If not, the model ends
model.terminate()I slove the sub_dual problem to get an upper bound and retrieve the current master problem's value to get a lower bound. However it converges to a wrong value(which is larger than the optimal minimal value). When I use the model.write('test.lp') and find that the constraint is not "model.getVarByName('q') >= lin".
I don't know what's wrong...???
0 -
Hi Jacob,
Lazy constraints added in a callback will not be part of the model written via the write method. This is because these lazy constraints are added during the optimization process.
If you want to check whether your lazy constraint is the correct one, you could print the linear expression \(\texttt{lin}\)
if abs(UB - LB) >= 0.01:
print(lin)
model.cbLazy(model.getVarByName('q') >= lin)This should help you in debugging your model.
Best regards,
Jaromił0 -
Hi, Jaromil! Thank you for replying me. I have some issues to consult...
(1) I have printed the linear expression and it's right. To testify whether the callback function works well, I add the linear expression as a user cut to the master problem. And
model.cbLazy(model.getVarByName('q') >= lin)retrieves a value different from the master problem's value after adding a user cut.
(2) I want to know how to retrieve the current node's value which gives a lower bound of the master problem.
LB = model.cbGet(GRB.Callback.MIPSOL_OBJ)
The code above gives the current objective value of a new feasible solution instead of the overall lower bound. Therefore, when I print the LB, the LB's value is not non-decreasing(which is -5000, 60.2, 0.6, 0.6, 0.4...) And it doesn't work(converge to a false value) if I make the model terminated when
abs(UB - LB) >= 0.01I should change many code as below:
if status == 2:
### add optimality cut
### When the UB and LB are not equal, add the optimality cut
if abs(UB - LB) >= 0.01:
model.cbLazy(model.getVarByName('q') >= lin)
#### model.write('test.lp')
else:
### If not, the model ends
### model.terminate()
pass0 -
I don't know why...? Can you give me some hints? Thank you so much~
0 -
Hi Jacob,
(1) If you know what should be or should be not the correct solution of the model with the previously added lazy constraint, one way to investigate would be to construct a model copy before starting the optimization, then adding the lazy constraint to this copy as a normal constraint and finally write the copied model to a file to investigate in more detail. You can achieve this by
# in your callback function
if abs(UB - LB) >= 0.01:
model.cbLazy(model.getVarByName('q') >= lin)
# add the same constraint to the copy
# it is possible because we are currently not optimizing model._copy
model._copy.addConstr(model._copy.get(VarByName('q') >= lin_copy)
model._copy.write("copyLP.lp")
# [...]
model._copy = model.copy()
model._copy_vars = model._copy.getVars()
model.optimize(mycallback)The tricky part is that you have to construct a \(\texttt{lin_copy}\) object using the variables from the copied model \(\texttt{model._copy}\). This should be a valid way to better debug your model.
(2) You can get the current best bound value via MIPSOL_OBJBND
LB = model.cbGet(GRB.Callback.MIPSOL_OBJBND)
The current best feasible point value can be obtained via MIPSOL_OBJBST.
Best regards,
Jaromił0 -
Hi, Jaromił!
It works, but I don't know why my former code worked. Apparently, it retrieve the false LB... Is there any detailed explanation about the work process of callback function(I have viewed https://www.gurobi.com/documentation/9.5/refman/py_cb_s.html)
You are so cool!!! How can we become a Gurobi expert like you 😆
0 -
Hi Jacob,
Happy to hear that your code works now. There is not much more to add about callbacks to what already is stated in the documentation. There really is not much "magic" behind the work process of a callback function. Whenever the algorithm is in a given state, a callback query is performed and checked whether the user asked for any data in their callback function. In a given state, e.g., MIPSOL, you can then access specific information which are needed by the solver itself in any case. Of course, one can raise the complexity of a callback function arbitrarily but the process behind it, i.e., how Gurobi works with it, remains the same. You might be interested in our recent webinar on advanced heuristics implemented via callbacks.
You are so cool!!! How can we become a Gurobi expert like you 😆
Thank you :) I really don't want to sound like one of my old Professors but it indeed helps to play around with optimization problems/models/techniques. This is the easiest way to learn what does work and what does not. With some practice, you can then begin to think of the actual reasons why something does work and why something else does not.
Best regards,
Jaromił0 -
Hi, Jaromił!
When I retrieve the false LB,
if status == 2:
### add optimality cut
### When the UB and LB are not equal, add the optimality cut
if abs(UB - LB) >= 0.01:
model.cbLazy(model.getVarByName('q') >= lin)
#### model.write('test.lp')
else:
### If not, the model ends
### model.terminate()
passif abs(UB - LB) <= 0.01, I do nothing instead of terminating the model. And It converges to correct value. I said it's "magic" because I don't know whether the callback function can compare the true LB with UB automatically? I printed the detailed callback function's working process(every true LB, false LB, UB) and found that the right code and wrong code gave the same working process(the same number of callback, the same converge value). It puzzles me so much。。。
0
Post is closed for comments.
Comments
10 comments