Algorithm Summary

Currently, SYMPHONY is what is known as a single-pool BCP algorithm.
The term *single-pool* refers to the fact that there is a single
central list of candidate subproblems to be processed, which is
maintained by the tree manager. Most sequential implementations use
such a single-pool scheme. However, other schemes may be used in
parallel implementations. For a description of various types of
parallel branch and bound, see [14].

The master module begins by reading in the parameters and problem data. After initial I/O is completed, subroutines for finding an initial upper bound and constructing the root node are executed. During construction of the root node, the user must designate the initial set of active cuts and variables, after which the data for the root node are sent to the tree manager to initialize the list of candidate nodes. The tree manager in turn sets up the cut pool module(s), the linear programming module(s), and the cut generator module(s). All LP modules are marked as idle. The algorithm is now ready for execution.

In the steady state, the tree manager functions control the execution by maintaining the list of candidate subproblems and sending them to the LP modules as they become idle. The LP modules receive nodes from the tree manager, process them, branch (if required), and send back the identity of the chosen branching object to the tree manager, which in turn generates the children and places them on the list of candidates to be processed (see Section 3.2.2 for a description of the branching operation). A schematic summary of the algorithm is shown in Figure 3.1.

The preference ordering for processing nodes is a run-time parameter.
Typically, the node with the smallest lower bound is chosen to be
processed next since this strategy minimizes the overall size of the
search tree. However, at times, it is advantageous to *dive*
down in the tree. The concepts of *diving* and *search
chains*, introduced in Section 3.2.3, extend the basic
``best-first'' approach.

We mentioned earlier that cuts and variables can be treated in a somewhat symmetric fashion. However, it should be clear by now that our current implementation favors the implementation of branch and cut algorithms, where the computational effort spent generating cuts dominates that of generating variables. Our methods of representation also clearly favor such problems. In a future version of the software, we plan to erase this bias by adding additional functionality for handling variable generation and storage. This is the approach already taken by of COIN/BCP [8]. For more discussion of the reasons for this bias and the differences between the treatment of cuts and variables, see Section 3.2.2.

2003-10-16