• Gurobi Staff

Gurobi does find an incumbent solution to this problem after 4521 seconds, which turns out to be optimal:

*684495  4903             148       0.0000000    0.00000  0.00%  78.4 4521s
...
Explored 688431 nodes (57063185 simplex iterations) in 4521.91 secondsThread count was 32 (of 48 available processors)
Solution count 1: 0
Optimal solution found (tolerance 1.00e-04)Best objective 0.000000000000e+00, best bound 0.000000000000e+00, gap 0.0000%

It took Gurobi over an hour to find this solution. This new incumbent solution had an objective value of $$0$$, which was equal to the dual bound of $$0$$. As a result, Gurobi determined the solution was optimal.

1. How does Gurobi know that the best bound is 0?

The original dual bound comes from the optimal objective value of the root relaxation:

Root relaxation: objective 0.000000e+00, 1865 iterations, 0.17 seconds

This is the problem you get by relaxing the integrality restrictions on all of the variables and solving the resulting LP. The feasible region of this relaxed problem is larger than the feasible region of your original problem. As a result, the optimal objective value of the relaxed problem is a lower bound (for minimization problems) on the optimal objective value of your original problem.

2. If there is no incumbent solution, does Gurobi do any pruning during the branch-and-bound process?

If Gurobi solves a node LP and determines it is infeasible, then the node will be pruned.

3. Is it possible to specify an upper bound so that Gurobi can prune branches according to this upper bound instead of relying on an incumbent solution to prune the branches? The parameters BestObjStop and BestBdStop caught my attention but it isn't clear whether they are used only to terminate the program or if they are used for pruning as well.

No - the only way to do this is to pass the corresponding solution to Gurobi as a MIP start. The solution provides proof that the upper/primal bound is valid. If the solution is feasible, Gurobi will use it as the initial incumbent solution.

In your case, because the initial dual bound is $$0$$, providing Gurobi with an incumbent solution with objective value $$0$$ will be enough to solve the problem almost instantly.

Thank you, Eli, for your clear answers. I have a better understanding of how to read the log file now. I'll see what I can do with MIP starts.

Best,

Omkar A. Katta