Skip to main content

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

Answered

Comments

3 comments

  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    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
    Conversationalist
    First Question

    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 Gurobi Staff

    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.