Please see the branch, cut, and price FAQ
SYMPHONY is a callable library for solving mixed-integer linear programs (MILPs) that can be customized through a wide variety of user callback functions and control parameters. It runs in both sequential and parallel environments (distributed- or shared-memory). SYMPHONY's core solution methodology is a branch and cut algorithm that incorporates most of the advanced solution management features available in other codes. Branch and cut is a technique for solving large-scale discrete optimization problems (see question below). For a more complete description of SYMPHONY, click here or see the on-line SYMPHONY manual.
Open-source software is software that is distributed under an open-source license. Open source license allow the user of the software certain rights, such as access to the source code and the ability to redistribute the software under certain conditions. The big advantage of open-source software is that the user has access to the inner workings and can participate directly in development efforts. This also allows development of highly specialized versions of the original code. All of the software available on this site is distributed under the Common Public License, an open source license used by the COIN-OR project. For more information on open-source development, visit the Open Source Initiative.
COIN-OR is the Computational Infrastructure for Operations Research project and is a consortium of researchers and practitioners from both academia and industry who support the development og open-source software tools for operations research. The project is run by the non-profit COIN-OR Foundation. The software available on this site is part of the COIN-OR software repository. All software available at this site uses COIN-OR's open-source license, called the Common Public License.
There is an extensive user's manual available both on-line and in PDF. The manual is included with the standard distribution. There is also a simple walkthrough guide to developing an application with SYMPHONY.
SYMPHONY has been used on most common Unix platforms. It has tested under the following operating systems
It should be easy to port to others as well.
- Microsoft Windows (serial mode only)
SYMPHONY is implemented in C, although it calls on some third-party codes written in C++ and will compile using a C++ compiler. SYMPHONY also has a C++ interface derived from the COIN-OR Open Solver Interface.
Starting with the SYMPHONY generic MILP solver, you customize the algorithm by providing problem-specific subroutines, such as functions for performing cut generation or branching, that inherently depend on problem structure. This is described in more detail in the documentation. There is also a quick start guide in the README file included with the distribution and in the user's manual.
There are a number of applications available for download that illustrate SYMPHONY development. There is also a generic template code that can be used as a starting point for customization.
SYMPHONY will read AMPL/GMPL files using GLPKs parser, or MPS file using COIN-OR's parser. It can also use FlopC++ as a modeling interface.
SYMPHONY requires the use of a third-party LP solver. The LP solver links with the framework through a defined interface. Through COIN-OR's Open Solver Interface, it is now possible to use most commonly available LP solvers, including a few open-source alternatives. There are also native interfaces to CPLEX and OSL that are slightly more efficient. SYMPHONY also relies on other third-party software for some functionality. For instance, SYMPHONY can use COIN-OR's Cut Generator Library for generating generic cutting planes, COIN-OR's MPS file parser for reading MPS files and GLPKs parser for reading in AMPL files. It can also use FlopC++ as a modeling interface. Most of the software needed is now included in the SYMPHONY distribution.
To run SYMPHONY in a distributed memory environment requires the use of a third-party communications protocol supporting basic message-passing functions. Currently, there is an interface to Parallel Virtual Machine, an open source message-passing library available for free download from Oak Ridge National Labs.
FOr information on getting the latest SYMPHONY packaged release, go here.
COIN/BCP is a C++ framework based roughly on an ancestor of SYMPHONY, so they take substantially the same approach and have similar functionality. COIN/BCP was developed at IBM and is also part of the COIN-OR software repository. Currently, SYMPHONY is easier to use "out of the box" and is a better choice for beginners. However, the most recent versions can only be used for implementing pure branch and cut (without column generation). COIN/BCP is much better than SYMPHONY in some areas, however, such as support for column generation. COIN/BCP is missing some features that SYMPHONY has, such as an implementation of global cut pools. SYMPHONY and COIN/BCP may be combined into a third-generation framework currently under development.
Although many excellent generic MILP solvers employing a version of the branch and cut algorithm are now available, most are not as flexible as framework like SYMPHONY, which is designed to allow the user to insert specialized methods that take advantage of problem structure. It is not possible to solve many of the toughest discrete optimization problems without problem-specific modifications to the generic algorithm. In recent versions of commercial MILP solvers such as CPLEX, it has become possible to add problem-specific cuts and customize certain features, but frameworks such as SYMPHONY are more flexible and support a much wider range of options. If you do not need to develop a custom code, then you are probably better off with a commercial MILP solver. Of course, having access to the full source code is also a big advantage of SYMPHONY and other open-source alternatives.
Yes. To subscribe to the SYMPHONY user's list serve, click here.
This page maintained by Ted Ralphs (email@example.com)
Last updated June 12, 2007