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. An LP process is allowed to 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.