Valid user cuts cut off optimal solution

Answered

Timo Gersing

February 09, 2022 12:05 Edited

• 
• 
• 

Dear all,

Short version: I encountered some issues with the separation of user cuts for a MIP, where adding valid inequalities (cuts) lead to a significant change in the optimal objective value. However, adding the exact same cuts to the model before calling optimize() worked out. This makes me believe that there might be a bug in the user cut callback.

Longer version: I try to solve several MIPs using branch-and-cut and wrote a separation algorithm for computing cuts in the callback. For most problems, everything works fine, but there are some issues with specific instances. I provide one of these in the model.mps file here. I do know the optimal objective value for these, as I solved the instances using other approaches before, and was surprised to see that adding the cuts within the callback lead to a significant worsening of the optimal objective value (-7.367e+09 instead of -7.916e+09 for a minimization problem, see Log_ActualComputation.txt).
At first, I thought that I might have some bugs in the separation algorithm leading to invalid cuts. Hence, I wrote the cuts to a separate file (see cuts.txt) and analyzed whether there would be any issues. However, it seemed like everything was correct. To further validate the cuts, I tried to add them to the model before calling optimize(), which results in the correct optimal objective value (see Log_CutsAddedToModel.txt). Therefore, the cuts themselves should not be the cause of the problem. The issue with separating the cuts can also be reproduced when adding all cuts from cuts.txt directly once within the first possible state of the callback (see Log_CutsAddedViaCallback.txt). You can test both, adding all cuts directly to the model and adding all within the callback, using the provided AddModelVSCallbackTester.java program.

I hope that I could describe the problem in an understandable way and look forward to feedback.

Best regards,
Timo

0

• 

  Maliheh Aramon

  • Gurobi Staff

  February 10, 2022 20:11

  Hi Timo, 

  Your explanation made perfect sense and we could reproduce your observations on our side using the latest Gurobi version 9.5.0. We will turn this into a ticket in our Support system and we will update you there after investigating this further. 

  Thank you for reporting this! 

  Maliheh

   

  0
• 

  Timo Gersing

  February 11, 2022 13:45

  • 
  • 
  • 

  Hi Maliheh,
  
  Thank you for the quick reply and checking the problem!
  I am already quite curious what the reason could be. :-)
  
  Have a nice day!
  Timo

  0

Please sign in to leave a comment.