SYMPHONY is a program 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.
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 GNU MathProg (AMPL subset) 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 can enter commands to execute and control the program.
Famous quotes containing the word symphony:
“The truth is, as every one knows, that the great artists of the world are never Puritans, and seldom even ordinarily respectable. No virtuous man—that is, virtuous in the Y.M.C.A. sense—has ever painted a picture worth looking at, or written a symphony worth hearing, or a book worth reading, and it is highly improbable that the thing has ever been done by a virtuous woman.”
—H.L. (Henry Lewis)