Back to SYMPHONY Home Page
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.