2
$\begingroup$

I understand how exploring the Branch-and-cut tree would help improve the best bound known and the incumbent of a MILP, however, on some instances that I deal with, my solver (Gurobi) seems to keep improving the best bound and the incumbent without exploring any node and on staying on node 0. It looks like it does not start the tree exploration.

Nodes    |    Current Node    |     Objective Bounds      |     Work
Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

 0     0 94578.3526    0  822 566233.300 94578.3526  83.3%     -  272s
 0     0 94578.3526    0  822 566233.300 94578.3526  83.3%     -  297s
 0     0 94578.3526    0  822 566233.300 94578.3526  83.3%     -  305s
 H     0     0                373429.30000 94578.3526  74.7%     -  314s
 0     0 97103.0161    0  896 373429.300 97103.0161  74.0%     -  352s

[...] One hour later

 H    0     0                 141739.31000 112400.671  20.7%     - 3239s
 0     0 112419.982    0 1143 141739.310 112419.982  20.7%     - 3249s
 0     0 112474.328    0 1156 141739.310 112474.328  20.6%     - 3266s
 0     0 112474.728    0 1146 141739.310 112474.728  20.6%     - 3277s
 0     0 112502.990    0 1159 141739.310 112502.990  20.6%     - 3313s
 0     0 112510.428    0 1168 141739.310 112510.428  20.6%     - 3335s
 0     0 112511.150    0 1169 141739.310 112511.150  20.6%     - 3347s
 0     0 112511.150    0 1182 141739.310 112511.150  20.6%     - 3378s
 H    0     0                 141433.66000 112511.150  20.4%     - 3402s
 0     0 112511.150    0 1181 141433.660 112511.150  20.4%     - 3407s

How is that explained? For which instances would that happen?

$\endgroup$

1 Answer 1

3
$\begingroup$

The solver generates and applies cuts at the root node. The cuts are designed to tighten the LP relaxation, which results (hopefully) in the best bound tightening. The solver also applies heuristics at the root node. The heuristics hopefully find new incumbents that improve the primal bound.

$\endgroup$
2
  • $\begingroup$ How does the solver decides to switch to the branching tree? $\endgroup$
    – JKHA
    Commented Feb 14 at 22:09
  • 1
    $\begingroup$ I imagine that varies from one solver to the next, but presumably it either runs out of cuts to try, hits an internal limit on number of cuts, or stops cutting after a predetermined number of cuts fail to improve anything. $\endgroup$
    – prubin
    Commented Feb 15 at 4:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.