Back to SYMPHONY Home Page
T.K. Ralphs
and L. Ladanyi
December 31, 1999
Postscript version available here
This white paper introduces SYMPHONY (Single- or Multi-Process Optimization over Networks), a powerful environment for implementing branch, cut, and price algorithms. SYMPHONY is a state-of-the-art solver which is designed to be completely modular and is easy to port to various problem settings. All library subroutines are generic--their implementation does not depend on the the problem-setting. To develop a full-scale, parallel branch, cut, and price algorithm, the user has only to specify a few problem-specific functions 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. SYMPHONY communicates with the user's routines through well-defined interfaces and performs all the normal functions of branch and cut--tree management, LP solution, cut pool management, as well as inter-process communication. Although there are default options, the user can also assert control over the behavior of SYMPHONY through a myriad of parameters and optional subroutines. SYMPHONY can be built in a variety of configurations, ranging from fully parallel to completely sequential, depending on the user's needs. The library runs serially on almost any platform, and can run in parallel in any environment supported by the PVM message-passing protocol.