T.K. Ralphs and L. Ladanyi
December 31, 1999
Postscript version available here
Revised June 7, 2000
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 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.