Behaviour of IntInf in the branch-and-cut tree search log

Answered

Marcus Garvie

• February 23, 2022 04:21

Hi everyone,

I've been running a very tough pure binary LP problem with zero objective function in Gurobi. I'm happy to wait several months if that's what it takes to get a solution. I have experimented with various parameters including tuning with smaller models. The question I have concerns the IntInf parameter in the Current Node column of the branch-and-cut tree search log. In another post someone made a comment that I interpreted to mean that the IntInf parameter ('number of integer infeasabilities' ?) should be going to zero. I attach a graph I plotted of IntInf against time (in seconds). The graph does suggest to me that IntInf is going to zero, and if things progress at roughly the same rate I estimate that IntInf will reach zero in about 6 - 10 weeks. So is my interpretation correct here? Does the log data here suggest I'm heading towards an optimal solution? Thank you, Marcus.

0

• 

  Jaromił Najman

  Gurobi Staff

  • February 24, 2022 14:46

  Hi Marcus,

  So is my interpretation correct here? Does the log data here suggest I'm heading towards an optimal solution?

  Yes, however, there are a few things you should consider. Optimally, the number of integer infeasibilities should decrease fast if the B&B algorithm proceeds deeper through the tree and is guaranteed to find a feasible solution through branching only at some point in time. However, it is not at all guaranteed that the graph you produced can be extrapolated in any way. In worst case, it is possible that the B&B has to branch every single variable which means that the IntInf graph would be way flatter and the estimated time to find a feasible solution way larger than the 6-10 weeks.

  Usually, deriving any meaningful information for the IntInf information is hard. You said, you experimented with smaller models. Was Gurobi able to solve these smaller models in a decent amount of time? What exactly is the difference between the smaller and the large model? Do you have a variable hint, you might pass to Gurobi? Given the complexity of the problem, did you consider any decomposition approaches?

  Best regards, 
  Jaromił

  0
• 

  Marcus Garvie

  • February 24, 2022 15:13

  

  

  

  Thank you Jaromił.

  Was Gurobi able to solve these smaller models in a decent amount of time?

  Yes. For a model that is very similar, Gurobi solved it in about a minute! Another related model (but not so similar), Gurobi solved in about 20 minutes.

  What exactly is the difference between the smaller and the large model?

  The only real difference is complexity. All models are solving large tiling problems. Problems with more tiles are more complex. However there does seem to be significant differences in how Gurobi is tackling these models. For the 'similar model' Gurobi gets a solution almost at the first zero node of the branch-and-cut tree search. However, for the big problem I'm trying to solve the node throughput for the branch-and-cut tree search is very slow. This is why I think tuning didn't work well. I've managed to get a better performance by experimenting with parameters for the 'related model', which spends a reasonable amount of time on the branch-and-cut tree search.  

  Do you have a variable hint, you might pass to Gurobi?

  I read the documentation for what you call a 'variable hint'. I'm not sure how to set these at the command line. The parameters that seem to work well for the 'related model' are 

  Presolve=2 SolutionLimit=1 Method=-1 MIPFocus=1 Heuristics=1

  I don't know what other parameters to try, although I am currently trying to set the NoRelHeurTime for a few days to see if I get a solution.

  Thank you,

  Marcus.

  0
• 

  Jaromił Najman

  Gurobi Staff

  • February 24, 2022 15:38

  To pass variable hints through the command line, you have to use a HNT file.

  I don't know what other parameters to try, although I am currently trying to set the NoRelHeurTime for a few days to see if I get a solution.

  No Relaxation Heuristic is a good idea to try. In general, finding feasible solution is an extremely difficult task. Especially, if the search space is very large. You could try using an objective function to guide Gurobi into a specific direction. It may help in finding a feasible solution. You can then terminate early by setting the SolutionLimit parameter to 1.

  Best regards, 
  Jaromił

  0

Please sign in to leave a comment.