Diving heuristics in branch and bound

Question

I am reading about extensions on plain vanilla B&B and heuristics for smaller trees/better branching. I have come across diving heuristics, which on the SCIP site is defined as:

A diving heuristic explores a single probing path down the search tree

What I understand reading this is that it branches using a depth-first-search rule. Does this make sense? If not, what does this mean, especially a single probing path?

Also, my other question is: when do we use this or other kinds of heuristics? I understand that heuristics can be used to find which variable to branch on (for example the most fractional), but how would I know when to explore a single path and when not to?

In another document, driving heuristics were under a section named "start heuristics". Does it mean that they are used to quickly find a feasible integer solution?

Answer 1

Diving heuristics are primarily used to find feasible points, and are more common in problems with integer variables.

Diving heuristics go down some branch of the tree until they (i) hit infeasibility, (ii) hit a pre-specified tree depth, or (iii) find a feasible point.

In cases (i) and (ii) the algorithm will backtrack and repeat the diving process down a different path, either from the root or some other pre-specified tree depth. Backtracking is also done sometimes in case (iii) in an attempt to find feasible points with even better objective values.

Diving can also be used to probe the results of branching and find an optimal variable selection sequence. This works by calculating the lower bounds for each node we explore. After we try $n$ paths, we then chose the branching sequence that produces the best bound after a pre-set number of branching operations.

My experience however has been that this tends not to be very efficient - in practice we prefer strong branching in the first few nodes of the tree, and then switch to a cheaper heuristic, such as pseudo-costs.

Regardless of the method used, it is well established that good branching choices in the beginning of the algorithm can reduce the total number of nodes we will have to explore significantly, therefore we are usually more than happy to spend some extra computing time in the beginning to run expensive heuristics.