How to set termination criteria for Master Problem?

Answered

Ibrahim Yilmazlar

October 02, 2022 21:31

Hello,

I formulated a two-stage 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

0

• 

  David Torres Sanchez

  • Gurobi Staff

  October 10, 2022 14:49

  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 1e-4
    else:
      mp.Params.MIPGap = 0.1 # for example
    iteration += 1

  However, 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.643-657.

  1

Please sign in to leave a comment.