Next: The Two-Phase Algorithm Up: The Tree Management Module Previous: Managing the Search Tree Contents
One reason for not strictly enforcing the search order is because it is somewhat expensive to construct a search node, send it to an NP module, and set it up for processing. If, after branching, we choose to continue processing one of the children of the current subproblem, we avoid the set-up cost, as well as the cost of communicating the node description of the retained child subproblem back to the tree manager. This is called diving and the resulting chain of nodes is called a search chain. There are a number of rules for deciding when an NP module should be allowed to dive. One such rule is to look at the number of variables in the current LP solution that have fractional values. When this number is low, there may be a good chance of finding a feasible integer solution quickly by diving. This rule has the advantage of not requiring any global information. We also dive if one of the children is “close” to being the best node, where “close” is defined by a chosen parameter.
In addition to the time saved by avoiding reconstruction of the LP in the child, diving has the advantage of often leading quickly to the discovery of feasible solutions, as discussed above. Good upper bounds not only allow earlier pruning of unpromising search chains, but also should decrease the time needed to process each search tree node by allowing variables to be fixed by reduced cost.