Stopping Criteria based on reduced gap per time

Answered

Ozge Aygul

May 18, 2023 16:48

• 
• 
• 

Hi,

I wonder if there is a way to stop solving the problem if the gap does not reduce significantly in a specified time. Because I have some instances that 5% gap is feasible, but for some instances, it takes over 40 minutes to reduce the gap from 6% to 5%. 

Is it possible to automate this process?

Thanks!

Özge 

Related to

• MIP Gap
• Termination

0

• 

  Maliheh Aramon

  • Gurobi Staff

  May 18, 2023 18:58 Edited

  Hi Özge, 

  You can implement custom termination criteria using Gurobi callbacks. 

  See the example code below for terminating the optimization of the model \(\texttt{model}\) if the gap does not decrease more than \(\epsilon\) for a given time period \(t\).

  import gurobipy as gp
  from gurobipy import GRB
  
  def callback(model, where):
      if where == GRB.Callback.MIP:
          runtime = model.cbGet(GRB.Callback.RUNTIME)
          incumbent = model.cbGet(GRB.Callback.MIP_OBJBST)
          bound = model.cbGet(GRB.Callback.MIP_OBJBND)
          gap = abs((bound - incumbent) / incumbent)
  
          # If an incumbent solution is found
          if incumbent != GRB.INFINITY:
              # If the current gap is different from the previous gap, update
              # the time_to_best and the gap
              if (model._gap - gap) > epsilon_to_compare_gap:
                  model._time_to_best = runtime
                  model._gap = gap
              # If the current gap is the same as the previous gap for more than
              # the time_from_best, terminate
              elif runtime - model._time_to_best > time_from_best:
                  model.terminate()
  
  # Global variables used in the callback function
  time_from_best = t
  epsilon_to_compare_gap = epsilon
  # Initialize data passed to the callback function via model._data
  model._gap, model._time_to_best = 1.0, float("inf")
  model.optimize(callback)

  Please also have a look at the article "How do I use callbacks to terminate the solver?".

  Best regards,

  Maliheh

  0
• 

  Ozge Aygul

  May 19, 2023 13:13

  • 
  • 
  • 

  Hi Maliheh,

  Thank you very much for your answer!

  I did apply the solution provided, with time_from_best = 300, epsilon_to_compare_gap = 0.1. I also set MIPGap parameter to 0.05.

  I thought the solver would be terminated if there was less than a 10% decrease in the gap in 300 seconds. In this case, the solver should have stopped when there was a 35% gap.

  Could you clarify this issue?

  Thank you very much!

  

  0
• 

  Maliheh Aramon

  • Gurobi Staff

  May 20, 2023 02:15

  Hi, 

  Thanks for reporting this. From the log, I would have expected that the solver terminates at time 6539 seconds with a gap 34.8%. To better investigate this, could you please share the MPS file of your model with us? Please note that you cannot attach a file, you will need to upload it in Google Drive or OneDrive for example and then share the link here.

  Best regards,

  Maliheh

  0
• 

  Ozge Aygul

  May 20, 2023 13:30

  • 
  • 
  • 

  Hi Maliheh,

  I think I made a mistake while implementing. Now, it works fine.

  Thank you very much for your help!

  Best, 

  Özge

  0

Please sign in to leave a comment.