7
$\begingroup$

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?

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thanks, this is helpful. I am wondering if diving heuristics (or others) are used every time we start a problem, meaning we use the following : Start node -> branch right -> diving heuristic -> if case (i) or (ii), come back to start node, then branch left -> diving heuristic and so on ... This means that we use this heuristic no matter what. $\endgroup$
    – VincFort
    Jan 30 '20 at 19:28
  • $\begingroup$ Yes, that's a good example of how this would work. $\endgroup$ Jan 30 '20 at 19:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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