Back to SYMPHONY Home Page
SYMPHONY (Single- or Multi-Process Optimization over Networks) is a state-of-the-art, parallel implementation of the branch, cut, and price algorithm, referred to henceforth as simply branch and cut. This general class of algorithm has long been the method of choice for solving hard combinatorial and general mixed-integer optimization problems. However, because of the inherent need for problem-dependent techniques (most notably separation), implementation has often been time-consuming and difficult. SYMPHONY seeks to minimize these difficulties by providing a generic library that implements the framework of the algorithm, while requiring the user to supply only those subroutines that depend on the problem setting.
To develop a full-scale, parallel branch, cut, and price algorithm, the user has only to supply a few problem-specific functions that depend on the problem setting, such as preprocessing and separation. The vast majority of the computation takes place within a ``black box,'' of which the user need have no knowledge. The internal library communicates with the user's routines through well-defined interfaces and performs all the normal functions of branch and cut--tree management, LP solution, and cut pool management, as well as inter-process communication. Although there are default options, the user can also assert control over the behavior of the algorithm through a myriad of parameters and optional subroutines. The executables can be built in a variety of configurations, ranging from completely sequential to fully parallel with independently functioning cut generators, cut pools, and LP solvers. The distributed version currently runs in any environment supported by the PVM message passing protocol. The same source code can also be compiled for shared-memory architectures using any OpenMP compliant compiler. SYMPHONY can be used in a variety of problem-settings and has already been ported to solve the Traveling Salesman Problem (TSP) ([15]), Vehicle Routing Problem (VRP) ([20, 14]), and the Set Partitioning Problem ([6]).