Incumbent solution is not changing (Improving the mipgap)

回答済み

Abodh Poudyal

2023年01月06日 19:10

• 
• 

Hello,

I am solving a MILP problem with about 72k continuous variables and 65k binary variables. As you can see below, the incumbent solution barely changes after the 8th hour, where the MIP gap is still 25%. After 36 hours, the gap decreases to 14%, at which point the bound changes slightly but not the incumbent solution.

1. Is this normal?

2. Is it safe to declare that the value of 1782.79 is somewhat optimal for this case? If not, is there any way to improve the optimality? I tried all the options of MIPFocus, NoRelHeur, and numeric focus, but nothing worked. I have also bounded all of the variables.

I would appreciate any help on this.

Regards,
Abodh

関連

• Performance

0

• 

  Jaromił Najman

  • Gurobi Staff

  2023年01月09日 09:58 編集済み

  Hi Abodh,

  1. Is this normal?

  The behavior you see is not unusual for complex models.

  2. Is it safe to declare that the value of 1782.79 is somewhat optimal for this case? If not, is there any way to improve the optimality? I tried all the options of MIPFocus, NoRelHeur, and numeric focus, but nothing worked. I have also bounded all of the variables.

  No, as there still might be a better feasible point. The possibly better feasible point won't be more than 14% better than the current one. However, if you have a guess about the optimal solution value and can say that the value of the best feasible solution should be around the currently found feasible solution value, then it might make sense to terminate the optimization process and use the best feasible solution found so far. Note that for this you need to use some problem and/or application knowledge.

  One option would be to generate the given model for a small-medium sized data set which can be solved within acceptable time. You could then try to improve Gurobi's performance by tuning its parameters. For that, you can either experiment with the parameters mentioned in Most important parameters or use Gurobi's parameter tuning tool (see Parameter tuning tool and Using the Automatic Parameter Tuning Tool). You say that you already experimented with some parameters. However, in this approach you should use a small-medium sized data set to not having to wait forever to see whether a parameter has an impact on the solver's performance.

  Another option would be to try to find a stronger formulation for your model. Maybe the Tech Talk on Converting Weak to Strong MIP Formulations might be helpful.

  Best regards, 
  Jaromił

  0

サインインしてコメントを残してください。