COIN-OR SYMPHONY

 ??? 

Operations research is, roughly, the analysis and optimization of business decisions using mathematics. COIN-OR is a library of (interoperable) software tools for optimization, and a development platform for open source projects in the OR community. SYMPHONY is one of those tools.

SYMPHONY is an acronym standing for Single- or Multi-Process Optimization over Networks. It is a callable library which can solve general Mixed Integer Programs (MIPs) over heterogeneous networks. It is an open source branch and cut framework for solving MIPs and is available as a part of COIN-OR. It can use CLP, CPLEX, XPRESS or other linear programming solvers to solve the underlying linear programs.

SYMPHONY: A MILP solver

SYMPHONY is a callable library which implements both sequential and parallel versions of branch, cut and price to solve MILPs. A branch, cut and price algorithm is similar to a branch and bound algorithm but additionally includes Cutting-plane methods and pricing algorithms. The user of the library can customize the algorithm in any number of ways by supplying application-specific subroutines for reading in custom data files, generating application-specific cutting planes, or applying custom branching rules, resulting in a customized state-of-the-art branch and cut algorithm. Most components of the algorithm, e.g., search tree management, management of linear programming solution, cut pool management, and communication management, are internal to the library and need not be touched by the user. The executables can be built in any number 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 reads files in both, the MPS (format) (through the COIN-OR MPS reader) and AMPL files (through the GLPK parser). SYMPHONY does not have an LP-Solver of its own, but can be used with solvers like Clp, Cplex, Xpress through the Osi-interface. The cuts are generated using COIN's cut generation library: CGL. SYMPHONY also has structure specific implementations for problems like the Traveling salesman problem, Vehicle routing problem, Set partitioning problem, Mixed postman problem etc. SYMPHONY also has an interactive shell where the user and enter commands to execute and control the program.

SYMPHONY is part of the COIN-OR initiative to provide open-source solutions for the optimization community. Its source-code, manuals and user applications are available from its home page. CVS version of the code is available from the COIN website.

Other non-commercial solvers for MIPs

• MINTO
• CBC
• GLPK
• Branch Cut and Price (BCP)
• abacus mip solver

See also

• COIN-OR
• CGL
• CLP
• OSI

References

• J.T. Linderoth and T.K. Ralphs, Noncommercial Software for Mixed-Integer Linear Programming, Integer Programming: Theory and Practice, John Karlof (ed.), CRC Press Operations Research Series, 2005, 253-303. (Working Paper Version PDF)

External links

• SYMPHONY Homepage
• COIN-OR, Computational Infrastructure for Operations Research