The Two-Phase Algorithm

If no heuristic subroutine is available for generating feasible
solutions quickly, then a unique two-phase algorithm can also be
invoked. In the two-phase method, the algorithm is first run to
completion on a specified set of core variables. Any node that would
have been pruned in the first phase is instead sent to a pool of
candidates for the second phase. If the set of core variables is
small, but well-chosen, this first phase should be finished quickly
and should result in a near-optimal solution. 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 is 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 thus priced out can be eliminated from the problem
globally. If we are successful at pricing out all of 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 leaf of the search tree produced during
the first phase. We then continue processing any node in which we fail
to price out all the variables.

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 the children of any node for which
each child has lower bound 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
avoid the task of processing each child individually.

2007-12-21