Debugging wrong MIPSOL_OBJBND

Barak Gross

• November 25, 2020 14:08

I have modeled some graph problem in which I add graphs cuts as a lazy constraint.
For some reason after some number of iterations the algorithm deduce a bound for MIPSOL_OBJBND that is incorrect.
I know that if I look at the right subgraph as input and give it to my model, it terminates successfully, but I suspect that one of the lazy constraint might have made MIPSOL_OBJBND too big, will be glad to understand how I can debug why the algorithm derived this bound.

0

• 

  Barak Gross

  • November 26, 2020 17:20

  

  

  

  BTW, I tried the following:
  * Saving all lazy constraints
  * Created a constraint : OBJ <= CORRECT BOUND
  * Found n - the first time that adding the OBJ constraint and the first n lazy constraint became infeasible
  * Ran IIS on the infeasible instance. But this part is the hard one, it takes A LOT of time (more than 20K seconds) and it seems like I need at least 600 inequalities... Which means that even when (and if) it terminates, I wont be able to debug what exactly is wrong with the lazy constraints.

  0
• 

  Tobias Achterberg

  Gurobi Staff

  • December 07, 2020 16:45

  What if instead of adding the OBJ <= CORRECT BOUND constraint you fix all the variables to their optimal solution values, add the n constraint that invalidated this solution and then calculate an IIS? This should very quickly yield a single constraint that is invalid for your solution.

  Regards,

  Tobias

   

  0

Please sign in to leave a comment.