COIN-OR SYMPHONY
From Wikipedia, the free encyclopedia
 |
This article lacks information on the notability (importance) of the subject matter. Please help improve this article by providing context for a general audience, especially in the lead section. This article has been tagged since October 2006. (help, talk) |
SYMPHONY is a software for solving a class of mathematical problems called Integer Programming (IP) problems and its variants. A Linear Programming problem is an optimization (mathematics) problem in which we want to maximize or minimize a linear objective function over a set of linear constraints. A Pure Integer Programming problem is a Linear Programming problem in which all the variables are allowed to assume only integer values. A Mixed Integer Programming (MIP) problem is similar to a Pure IP Problem, but only some of the variables are constrained to be integers. Other variables can assume non-integral values. MIPs are useful in modelling a lot of real life problems in logistics, scheduling, production planning, finance and management sciences. They are also extensively used in theoretical research like combinatorics, statistics, physics and computational biology. MIPs are therefore, an important tool in the field of Operations research (OR), which is, roughly, the analysis and optimization of business and other 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.
Contents |
[edit] SYMPHONY: A MILP solver
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 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.
[edit] Other non-commercial solvers for MIPs
[edit] See also
[edit] 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)
[edit] External links
- SYMPHONY Homepage
- COIN-OR, Computational Infrastructure for Operations Research
