COIN-OR
Encyclopedia
COIN-OR, which stands for Computational Infrastructure for Operations Research
, is a project that aims to "create for mathematical software what the open literature is for mathematical theory
." The open literature (e.g., a research journal) provides the OR community with a peer-review process and an archive. Papers in operations research journals on mathematical theory often contain supporting numerical results from computational studies. The software implementations, models, and data used to produce the numerical results are typically not published. The status quo impeded researchers needing to reproduce computational results, make fair comparisons, and extend the state of the art.
The success of Linux
, Apache
, and other projects popularized the open-source model of software development and distribution. A group at IBM
Research proposed open source
as an analogous yet viable means to "publish" software, models, and data. COIN-OR was conceived as an initiative to promote open-source in the computational Operations Research
community and to provide the on-line resources and hosting services required to enable others to run their own open-source software projects.
The COIN-OR website was launched as an experiment in 2000, in conjunction with 17th International Symposium on Math Programming in Atlanta, Georgia. In the year 2007, COIN-OR had 25 application projects, including tools for linear programming
(e.g., COIN-OR CLP), nonlinear programming
(e.g., IPOPT
), integer programming
(e.g., CBC, Bcp and COIN-OR SYMPHONY) and more. COIN-OR is hosted by the Institute for Operations Research and the Management Sciences, INFORMS, and run by the educational, non-profit COIN-OR Foundation.
(NSF) workshop on Cyberinfrastructure and OR, only 3 examples were given: COIN-OR, NEOS, and CONDOR. Funded proposals of NSF awardees include publishing their work on COIN-OR (e.g).
Novel work in non-linear mixed-integer programming: Bonmin was only made possible by having access to linear programming solver source code (Clp), non-linear programming solver source code (IPOPT), branch-and-cut source code (Cbc), cut generation library (Cgl), interfaces and expertise made possible by COIN-OR.)
The first DIMACS workshop on COIN-OR was held in 2006.
COIN-OR (circa 2000) promoted open source as a model for university collaborations.
. CLP is an open-source
linear programming
solver
written in C++
. It is published under the Common Public License
so it can be used in commercial software without any of the contamination issues of the GNU General Public License
. CLP is primarily meant to be used as a callable library, although a stand-alone executable version can be built. It is designed to be as reliable as any commercial solver (if not quite as fast) and to be able to tackle very large problems.
CLP is designed to solve linear programming
problems such as :
with up to millions of variables and/or constraints. Its main algorithm is the Simplex algorithm
.
CLP is used in other COIN-OR projects such as SYMPHONY, BCP (Branch Cut and Price), CBC (Coin Branch and Cut) and others.
(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 method
s 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.
Operations research
Operations research is an interdisciplinary mathematical science that focuses on the effective use of technology by organizations...
, is a project that aims to "create for mathematical software what the open literature is for mathematical theory
Theory
The English word theory was derived from a technical term in Ancient Greek philosophy. The word theoria, , meant "a looking at, viewing, beholding", and referring to contemplation or speculation, as opposed to action...
." The open literature (e.g., a research journal) provides the OR community with a peer-review process and an archive. Papers in operations research journals on mathematical theory often contain supporting numerical results from computational studies. The software implementations, models, and data used to produce the numerical results are typically not published. The status quo impeded researchers needing to reproduce computational results, make fair comparisons, and extend the state of the art.
The success of Linux
Linux
Linux is a Unix-like computer operating system assembled under the model of free and open source software development and distribution. The defining component of any Linux system is the Linux kernel, an operating system kernel first released October 5, 1991 by Linus Torvalds...
, Apache
Apache HTTP Server
The Apache HTTP Server, commonly referred to as Apache , is web server software notable for playing a key role in the initial growth of the World Wide Web. In 2009 it became the first web server software to surpass the 100 million website milestone...
, and other projects popularized the open-source model of software development and distribution. A group at IBM
IBM
International Business Machines Corporation or IBM is an American multinational technology and consulting corporation headquartered in Armonk, New York, United States. IBM manufactures and sells computer hardware and software, and it offers infrastructure, hosting and consulting services in areas...
Research proposed open source
Open source
The term open source describes practices in production and development that promote access to the end product's source materials. Some consider open source a philosophy, others consider it a pragmatic methodology...
as an analogous yet viable means to "publish" software, models, and data. COIN-OR was conceived as an initiative to promote open-source in the computational Operations Research
Operations research
Operations research is an interdisciplinary mathematical science that focuses on the effective use of technology by organizations...
community and to provide the on-line resources and hosting services required to enable others to run their own open-source software projects.
The COIN-OR website was launched as an experiment in 2000, in conjunction with 17th International Symposium on Math Programming in Atlanta, Georgia. In the year 2007, COIN-OR had 25 application projects, including tools for linear programming
Linear programming
Linear programming is a mathematical method for determining a way to achieve the best outcome in a given mathematical model for some list of requirements represented as linear relationships...
(e.g., COIN-OR CLP), nonlinear programming
Nonlinear programming
In mathematics, nonlinear programming is the process of solving a system of equalities and inequalities, collectively termed constraints, over a set of unknown real variables, along with an objective function to be maximized or minimized, where some of the constraints or the objective function are...
(e.g., IPOPT
IPOPT
IPOPT, short for "Interior Point OPTimizer, pronounced I-P-Opt", is a software library for large scale nonlinear optimization of continuous systems. It is written in Fortran and C and is released under the EPL . IPOPT implements a primal-dual interior point method, and uses line searches based on...
), integer programming
Integer programming
An integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers. In many settings the term refers to integer linear programming, which is also known as mixed integer programming.Integer programming is NP-hard...
(e.g., CBC, Bcp and COIN-OR SYMPHONY) and more. COIN-OR is hosted by the Institute for Operations Research and the Management Sciences, INFORMS, and run by the educational, non-profit COIN-OR Foundation.
Significance
COIN-OR has attraction from both the research oriented and the application oriented organizations. At the National Science FoundationNational Science Foundation
The National Science Foundation is a United States government agency that supports fundamental research and education in all the non-medical fields of science and engineering. Its medical counterpart is the National Institutes of Health...
(NSF) workshop on Cyberinfrastructure and OR, only 3 examples were given: COIN-OR, NEOS, and CONDOR. Funded proposals of NSF awardees include publishing their work on COIN-OR (e.g).
- COIN-OR is changing the way research is done in the field of OR/MS.
Novel work in non-linear mixed-integer programming: Bonmin was only made possible by having access to linear programming solver source code (Clp), non-linear programming solver source code (IPOPT), branch-and-cut source code (Cbc), cut generation library (Cgl), interfaces and expertise made possible by COIN-OR.)
- COIN-OR is recognized by the Center for Discrete Mathematics and Theoretical Computer Science (DIMACSDIMACSThe Center for Discrete Mathematics and Theoretical Computer Science is a collaboration between Rutgers University, Princeton University, and the research firms AT&T, Bell Labs, Telcordia, and NEC. It was founded in 1989 with money from the National Science Foundation...
).
The first DIMACS workshop on COIN-OR was held in 2006.
- COIN-OR provoked the creation of the Common Public LicenseCommon Public LicenseIn computing, the CPL is a free software / open-source software license published by IBM. The Free Software Foundation and Open Source Initiative have approved the license terms of the CPL....
. - COIN-OR changed IBM Research.
COIN-OR (circa 2000) promoted open source as a model for university collaborations.
- COIN-OR is referenced in the scientific literature.
- COIN-OR is being used by business.
CLP
CLP stands for COIN-OR LPLinear programming
Linear programming is a mathematical method for determining a way to achieve the best outcome in a given mathematical model for some list of requirements represented as linear relationships...
. CLP is an open-source
Open source
The term open source describes practices in production and development that promote access to the end product's source materials. Some consider open source a philosophy, others consider it a pragmatic methodology...
linear programming
Linear programming
Linear programming is a mathematical method for determining a way to achieve the best outcome in a given mathematical model for some list of requirements represented as linear relationships...
solver
Solver
A solver is a generic term indicating a piece of mathematical software, possibly in the form of a stand-alone computer program or as a software library, that 'solves' a mathematical problem. A solver takes problem descriptions in some sort of generic form and calculate their solution...
written in C++
C++
C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell...
. It is published under the Common Public License
Common Public License
In computing, the CPL is a free software / open-source software license published by IBM. The Free Software Foundation and Open Source Initiative have approved the license terms of the CPL....
so it can be used in commercial software without any of the contamination issues of the GNU General Public License
GNU General Public License
The GNU General Public License is the most widely used free software license, originally written by Richard Stallman for the GNU Project....
. CLP is primarily meant to be used as a callable library, although a stand-alone executable version can be built. It is designed to be as reliable as any commercial solver (if not quite as fast) and to be able to tackle very large problems.
CLP is designed to solve linear programming
Linear programming
Linear programming is a mathematical method for determining a way to achieve the best outcome in a given mathematical model for some list of requirements represented as linear relationships...
problems such as :
-
- minimize
- subject to problem constraints of the following form
-
-
-
- Non-negative variables
-
-
- minimize
with up to millions of variables and/or constraints. Its main algorithm is the Simplex algorithm
Simplex algorithm
In mathematical optimization, Dantzig's simplex algorithm is a popular algorithm for linear programming. The journal Computing in Science and Engineering listed it as one of the top 10 algorithms of the twentieth century....
.
CLP is used in other COIN-OR projects such as SYMPHONY, BCP (Branch Cut and Price), CBC (Coin Branch and Cut) and others.
SYMPHONY
SYMPHONY is a program for solving a class of mathematical problems called integer programmingInteger programming
An integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers. In many settings the term refers to integer linear programming, which is also known as mixed integer programming.Integer programming is NP-hard...
(IP) problems and its variants. A linear programming
Linear programming
Linear programming is a mathematical method for determining a way to achieve the best outcome in a given mathematical model for some list of requirements represented as linear relationships...
problem is an optimization (mathematics)
Optimization (mathematics)
In mathematics, computational science, or management science, mathematical optimization refers to the selection of a best element from some set of available alternatives....
problem in which we want to maximize or minimize a linear
Linear
In mathematics, a linear map or function f is a function which satisfies the following two properties:* Additivity : f = f + f...
objective function over a set of linear
Linear
In mathematics, a linear map or function f is a function which satisfies the following two properties:* Additivity : f = f + f...
constraints. A Pure Integer Programming problem is a Linear Programming
Linear programming
Linear programming is a mathematical method for determining a way to achieve the best outcome in a given mathematical model for some list of requirements represented as linear relationships...
problem in which all the variables are allowed to assume only integer
Integer
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
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
Operations research
Operations research is an interdisciplinary mathematical science that focuses on the effective use of technology by organizations...
(OR), which is, roughly, the analysis and optimization of business
Business
A business is an organization engaged in the trade of goods, services, or both to consumers. Businesses are predominant in capitalist economies, where most of them are privately owned and administered to earn profit to increase the wealth of their owners. Businesses may also be not-for-profit...
and other decisions using mathematics
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
.
SYMPHONY is an acronym standing for Single- or multi-process
Parallel computing
Parallel computing is a form of computation in which many calculations are carried out simultaneously, operating on the principle that large problems can often be divided into smaller ones, which are then solved concurrently . There are several different forms of parallel computing: bit-level,...
optimization
Optimization (mathematics)
In mathematics, computational science, or management science, mathematical optimization refers to the selection of a best element from some set of available alternatives....
over networks
Network theory
Network theory is an area of computer science and network science and part of graph theory. It has application in many disciplines including statistical physics, particle physics, computer science, biology, economics, operations research, and sociology...
. It is a callable library which can solve general mixed integer programs
Linear programming
Linear programming is a mathematical method for determining a way to achieve the best outcome in a given mathematical model for some list of requirements represented as linear relationships...
(MIPs) over heterogeneous networks. It is an open source branch and cut
Branch and cut
Branch and cut is a method of combinatorial optimization for solving integer linear programs, that is, linear programming problems where some or all the unknowns are restricted to integer values...
framework for solving MIPs and is available as a part of COIN-OR. It can use CLP, CPLEX
CPLEX
IBM ILOG CPLEX Optimization Studio is an optimization software package. In 2004, the work on CPLEX earned the first ....
, XPRESS or other linear programming
Linear programming
Linear programming is a mathematical method for determining a way to achieve the best outcome in a given mathematical model for some list of requirements represented as linear relationships...
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
Branch and bound
Branch and bound is a general algorithm for finding optimal solutions of various optimization problems, especially in discrete and combinatorial optimization...
algorithm but additionally includes Cutting-plane method
Cutting-plane method
In mathematical optimization, the cutting-plane method is an umbrella term for optimization methods which iteratively refine a feasible set or objective function by means of linear inequalities, termed cuts...
s 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
OpenMP
OpenMP is an API that supports multi-platform shared memory multiprocessing programming in C, C++, and Fortran, on most processor architectures and operating systems, including Linux, Unix, AIX, Solaris, Mac OS X, and Microsoft Windows platforms...
compliant compiler.
SYMPHONY reads files in both, the MPS (format)
MPS (format)
MPS is a file format for presenting and archiving linear programming and mixed integer programming problems.- Overview :...
(through the COIN-OR MPS reader) and GNU MathProg (AMPL
AMPL
AMPL, an acronym for "A Mathematical Programming Language", is an algebraic modeling language for describing and solving high-complexity problems for large-scale mathematical computation AMPL, an acronym for "A Mathematical Programming Language", is an algebraic modeling language for describing and...
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
Vehicle routing problem
The vehicle routing problem is a combinatorial optimization and integer programming problem seeking to service a number of customers with a fleet of vehicles. Proposed by Dantzig and Ramser in 1959, VRP is an important problem in the fields of transportation, distribution and logistics...
, 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.
Further reading
- 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
- COIN-OR solvers are available in the AIMMSAIMMSAIMMS is a software system designed for modeling and solving large-scale optimization and scheduling-type problems....
, AMPLAMPLAMPL, an acronym for "A Mathematical Programming Language", is an algebraic modeling language for describing and solving high-complexity problems for large-scale mathematical computation AMPL, an acronym for "A Mathematical Programming Language", is an algebraic modeling language for describing and...
and GAMSGeneral Algebraic Modeling SystemThe General Algebraic Modeling System is a high-level modeling system for mathematical optimization. GAMS is designed for modeling and solving linear, nonlinear, and mixed-integer optimization problems. The system is tailored for complex, large-scale modeling applications and allows the user to...
modeling systems as well as in the FortSPFortSPFortSP is a software package for solving stochastic programming problems. It solves scenario-based SP problems with recourse as well as problems with chance constraints and integrated chance constraints...
solver