How to set termination criteria for Master Problem?
AnsweredHello,
I formulated a twostage stochastic problem and implemented Benders' Decomposition method via Gurobi callback. I add several lazy cuts at each iteration ("where == GRB.Callback.MIPSOL"). The master problem (MP) gets very large after a while and it takes a lot of time to solve it. However, it is not necessary to solve the MP to optimality at every iteration in order to achieve global convergence.
1) Is there a way to set dynamic termination criteria for MP, e.g. solve MP optimally once in every 10 iterations?
2) About MP size management: I know that I cannot remove any constraints in the callback. Could you provide any recommendations about how to remove some lazy cuts?
 I tried storing the cuts and adding only when they improve the incumbent solution but the algorithm converges to a wrong optimal solution.
Note: All the cuts are optimality cuts since any solution is feasible.
Thank you in advance
Ibrahim Yilmazlar

Hi Ibrahim,
These should be straightforward.
1) Is there a way to set dynamic termination criteria for MP, e.g. solve MP optimally once in every 10 iterations?
For example,
# formulate Model: mp
iteration = 0
while iter_criteria:
if iteration % 10 == 0:
mp.Params.MIPGap = 0 # or default of 1e4
else:
mp.Params.MIPGap = 0.1 # for example
iteration += 1However, doing this will result in "inexact" cuts and you should check if you can make a claim about the optimality of the procedure (Zakeri et al. 2000).
2) About MP size management: I know that I cannot remove any constraints in the callback. Could you provide any recommendations about how to remove some lazy cuts?
 I tried storing the cuts and adding only when they improve the incumbent solution but the algorithm converges to a wrong optimal solution.
Have you tried to just add all lazy constraints? Gurobi will use the ones that help.
You could also try adding each cut as a new constraint to the master problem iteratively instead of using a callback. This may bring some speedup as Gurobi will be able to apply presolve more effectively.
To my limited understanding, after every subproblem you should always have a valid cut (optimality or feasibility cut, otherwise you should terminate).Cheers,
David
Zakeri, G., Philpott, A.B. and Ryan, D.M., 2000. Inexact cuts in Benders decomposition. SIAM Journal on Optimization, 10(3), pp.643657.
1
Please sign in to leave a comment.
Comments
1 comment