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 [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.

2010-03-24