Estimating the time it takes to solve a MIP is very difficult. The nature of NP-hard problems is that they can take a very long time to solve or may not even be solvable in a reasonable amount of time. Due to a large variety of many highly advanced solution techniques and tricks, Gurobi is often able to find solutions quickly - even for large models. In addition, there are seemingly easy problems that are very hard to solve.
Understanding Gurobi's log output can help you have a better idea of the current solver status. This section in the documentation for detailed information about the log output provides a good overview of the information that is reported. Most relevant for estimating the remaining time are:
- the progress in the MIPGap column and
- the number of unexplored (or open) nodes in the second column.
MIPGap
If the MIPGap has been decreasing steadily, the gap is likely to continue to decrease - either by finding new solutions (H or * markers) or by improving the dual bound.
Unexplored nodes
The unexplored node count reports how many nodes have been created via branching but have not yet been processed. If this number continues to grow, the solver is likely still far away from proving optimality. On the other hand, a new incumbent might cut off a huge part of the search tree and decrease this number very suddenly.
Further reading
Estimating the MIP tree size and hence the remaining time to solve a model is a topic of ongoing research. One possible starting point for further study can be found in this article:
Further information
- MIP Logging section in the Reference Manual
- How do I instruct Gurobi to produce a log file?