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.
Back to SYMPHONY Home Page