Next: Details of the Implementation Up: Design of SYMPHONY Previous: The Cut Management Module Contents
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 [16].
The user begins by initializing the SYMPHONY environment and can then invoke subroutines for reading in parameters and problem data, finding an initial upper bound, and designating the initial set of active cuts and variables in the root node. Once the user invokes a solve routine, a tree manager is created to manage the solution process. The tree manager module in turn sets up the cut pool module(s), the linear programming module(s), and the cut generator module(s). Currently, there are three solve calls supported by the API. The first call is the initial solve (see Section 4.4.1.1), which solves the problem from scratch without using warm start information. The second type of solve call is a warm solve, which solves the problem using previously computed warm start information (see Section 4.4.1.2). Finally, there is a multicriteria solve call which is used to enumerate efficient solutions to a given multicriteria MILP (see Section 4.4.1.3).
During the solution process, the tree manager functions control the execution by maintaining the list of candidate subproblems and sending them to the NP modules as they become idle. The NP 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 4.4.2.3 for a description of the branching operation). A schematic summary of the algorithm is shown in Figure 4.4. 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 4.4.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 [24]. For more discussion of the reasons for this bias and the differences between the treatment of cuts and variables, see Section 4.4.2.2.