How to set termination criteria for Master Problem?

回答済み

Ibrahim Yilmazlar

2022年10月02日 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

• 正式なコメント

  

  Simranjit Kaur

  • Gurobi Staff

  2025年11月16日 23:27

  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 try Gurobot, our chatbot interface offering instant, expert-level support.
• 

  David Torres Sanchez

  • Gurobi Staff

  2022年10月10日 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

投稿コメントは受け付けていません。