next up previous external Back to SYMPHONY Home Page
Next: Fault Tolerance Up: The Tree Manager Process Previous: Managing the Search Tree

The Two-Phase Algorithm

 

In the two-phase method, we first run the algorithm to completion on the specified set of base variables. Any node that would have been pruned in the first phase is sent to a pool of candidates for the second phase instead. If the set of base variables is small, but well-chosen, this first phase should be quick and should result in a near-optimal solution, and hence a good upper bound. In addition, the first phase will produce a list of useful cuts. Using the upper bound and the list of cuts from the first phase, the root node is repriced--that is, it is reprocessed with the full set of variables and cuts, the hope being that most or all of the variables not included in the first phase will be priced out of the problem in the new root node. Any variable so priced out can be eliminated from the problem globally. If we are successful at pricing out all the inactive variables, we have shown that the solution from the first phase was, in fact, optimal. If not, we must go back and price out the (reduced) set of extra variables in each one of the leaves of the search tree produced during the first phase. We then continue processing any node in which variables are consequently added to the relaxation.

In order to avoid pricing variables in every leaf of the tree, we can trim the tree before the start of the second phase. Trimming the tree consists of eliminating from the tree the children of any node whose aforementioned children all have lower bounds above the current upper bound. We then reprocess the parent node itself. This is typically more efficient since there is a high probability that, given the new upper bound and cuts, we will be able to prune the parent node and save the work of processing each child individually.


next up previous external
Next: Fault Tolerance Up: The Tree Manager Process Previous: Managing the Search Tree

Ted Ralphs
Thu Jun 8 14:31:17 CDT 2000