Skip to main content

Is it possible to change when (the gap %level) Gurobi starts focusing on finding feasible solutions instead finding a lower lower bound?

Answered

Comments

5 comments

  • Simranjit Kaur
    Gurobi Staff Gurobi Staff

    Hi Gaurav,

    The parameter ImproveStartGap allows you to specify a gap at which the solver switches to a strategy that will focus on finding better feasible solutions. 

    A manual approach will be to stop the solve at your desired gap, change parameters to focus on finding feasible solutions and start the solve again. The parameters that generally help with finding feasible solutions are MIPFocus(=1), NoRelHeurTime, and Heuristics.

    Best regards,
    Simran

    0
  • Gaurav Malik
    Conversationalist
    First Question

    Hello Simran,

    Thanks for your reply!
    If I set the parameter ImproveStartGap = 0.5, then would it completely give up on moving the best bound?
    I would instead prefer that after a certain gap, the solver alternates between strategies of improving the feasible solution and that of improving the lower bound. 
    If it completely gives up of moving the lower bound, then wouldn't it lead to cases where the problem is never solved as even at the optimal there is some gap left?
    Regards
    Gaurav

    0
  • Simranjit Kaur
    Gurobi Staff Gurobi Staff

    Hi Gaurav,

    With ImproveStartGap = 0.5, after the solver reaches a mip gap of 50%, it will give up on bound improvement and focus entirely on finding feasible solutions.

    I would instead prefer that after a certain gap, the solver alternates between strategies of improving the feasible solution and that of improving the lower bound. 

    To do this, you can change the relevant parameters in the MIP callback. For example, the script below starts solving the glass4.mps instance (distributed with the Gurobi software) with default settings, terminates optimization in the callback as soon as it reaches the mip gap of 50%, sets MipFocus=1 to focus on finding feasible solutions, continues optimization for the next 5 seconds, terminates the optimization again in the callback, sets MipFocus=2 to focus on improving bound, and continues optimization again. 

    import gurobipy as gp
    from gurobipy import GRB

    def my_callback(model, where):
      if where == GRB.Callback.MIP:
          run_time = model.cbGet(GRB.Callback.RUNTIME)
          objbst = model.cbGet(GRB.Callback.MIP_OBJBST)
          objbnd = model.cbGet(GRB.Callback.MIP_OBJBND)
          if abs(objbst - objbnd) < change_gap * (1.0 + abs(objbst)) and check_gap:
              m._changeParam_focusSol = True
              model.terminate()       

          if run_time > change_time and check_time:
              model._changeParam_focusBound = True
                model.terminate()

    change_gap=0.5
    change_time=5
    check_gap = True
    check_time = False

    m = gp.read('glass4.mps')
    m._changeParam_focusSol = False
    m._changeParam_focusBound = False
    m.optimize(my_callback)

    if m._changeParam_focusSol:
      m.params.MIPFocus = 1
      check_gap = False
      check_time = True
      m.optimize(my_callback)
      if m._changeParam_focusBound:
          m.params.MIPFocus=2
            m.optimize()

    If it completely gives up of moving the lower bound, then wouldn't it lead to cases where the problem is never solved as even at the optimal there is some gap left?

    Yes, you are correct; the solver may not terminate if the gap cannot be reduced to the MIPGap parameter value by only finding feasible solutions (for example, when the optimal solution is found in the improvement phase but the gap is still high due to a weak bound), and there are no other terminating criteria.

    Best regards,
    Simran

    0
  • Gaurav Malik
    Conversationalist
    First Question

    Thanks Simran!
    This looks like exactly what I needed. I will test it and get back to you. One question though:
    I think (please confirm) that when m.optimize() is called for the second and then for the 3rd time, it actually continues the same optimization routine and doesn't start optimizing from the beginning.  

    Regards

    Gaurav

    0
  • Simranjit Kaur
    Gurobi Staff Gurobi Staff

    Yes, the solver will continue the same optimization run with updated parameters in the second and third optimize() call.

    0

Please sign in to leave a comment.