Back to SYMPHONY Home Page
The tree manager's primary job is to control the execution of the algorithm by deciding which candidate node should be chosen as the next to be processed. This is done using one of the several built-in rules such as selecting the node with the lowest lower bound. Because it is expensive to construct a search node from scratch, the tree manager will often allow an LP process to retain one of the children resulting from branching in order to avoid the set-up costs associated with redistributing that node at a later time. This is called diving and the resulting chain of nodes is called a search chain. There are various rules available for deciding when an LP process should be allowed to dive. One such rule is to look at the number of variables in the current LP solution that are fractional. When this number is low, there is a good chance of finding a feasible solution quickly by diving. 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 apparent advantage of leading to the discovery of feasible solutions quickly. Since every feasible solution lies at the end of a search chain, it seems reasonable to dive periodically. Therefore, random diving takes place according to a specified parameter.