Next: Data Structures and Storage Up: Design of SYMPHONY Previous: Design of SYMPHONY Contents
As we have already alluded to, applying BCP to large-scale problems presents several difficult challenges. First and foremost is designing methods and data structures capable of handling the potentially huge numbers of cuts and variables that need to be accounted for during the solution process. The dynamic nature of the algorithm requires that we must also be able to efficiently move cuts and variables in and out of the active set of each search node at any time. A second, closely-related challenge is that of effectively dealing with the very large search trees that can be generated for difficult problem instances. This involves not only the important question of how to store the data, but also how to move it between modules during parallel execution. A final challenge in developing a generic framework, such as SYMPHONY, is to deal with these issues using a problem-independent approach.
Describing a node in the search tree consists of, among other things, specifying which cuts and variables are initially active in the subproblem. In fact, the vast majority of the methods in BCP that depend on the model are related to generating, manipulating, and storing the cuts and variables. Hence, SYMPHONY can be considered an object-oriented framework with the central “objects” being the cuts and variables. From the user's perspective, implementing a BCP algorithm using SYMPHONY consists primarily of specifying various properties of objects, such as how they are generated, how they are represented, and how they should be realized within the context of a particular subproblem.
With this approach, we achieved the “black box” structure by separating these problem-specific functions from the rest of the implementation. The internal library interfaces with the user's subroutines through a well-defined Application Program Interface (API) (see Section 6.3) and independently performs all the normal functions of BCP—tree management, LP solution, and cut pool management, as well as inter-process communication (when parallelism is employed). Although there are default options for many of the operations, the user can also assert control over the behavior of the algorithm by overriding the default methods or by parameter setting.
Although we have described our approach as being “object-oriented,” we would like to point out that SYMPHONY is implemented in C, not C++. To avoid inefficiencies and enhance the modularity of the code (allowing for easy parallelization), we used a more “function-oriented” approach for the implementation of certain aspects of the framework. For instance, methods used for communicating data between modules are not naturally “object-oriented” because the type of data being communicated is usually not known by the message-passing interface. It is also common that efficiency considerations require that a particular method be performed on a whole set of objects at once rather than on just a single object. Simply invoking the same method sequentially on each of the members of the set can be extremely inefficient. In these cases, it is far better to define a method which operates on the whole set at once. In order to overcome these problems, we have also defined a set of interface functions, which are associated with the computational modules. These function is described in detail in Section 6.3.