Forum
The COIN-OR Initiative:
Open-source software accelerates operations research progress
Every profession has its tools. Carpenters have nail guns, surgeons have scalpels, and operations researchers have computers. Computer software is fundamental to the field of operations research. Most practitioners depend on software implementations of OR models and algorithms to deliver value to their customers. Many academics rely on implementations of new algorithms to validate their research ideas. OR's dependence on software means that the way software is developed, managed and distributed can have a significant impact on the progress of the field.
Recently, a new software development and distribution model with significant advantages — open source — has emerged from the computer science community. The COIN-OR initiative promotes the new model to the OR community. [1]
Limitations of Current Software Practices
Progress in OR relies on a synthesis of advances in algorithms, software and hardware. But even in the academic community, where a premium is placed on open dissemination of theory, a much different custom prevails regarding the dissemination of software. OR publications often contain computational results as a complement to theorems, proofs and algorithms. While the theoretical details are routinely published, the implementations are not. There are good reasons for this custom; nevertheless, when the source code is not publicly available in some form, progress in the field is hampered in the following ways:
- Software reuse is impeded. Without access to source code, researchers are forced to reinvent rather than reuse existing code. Time and effort spent reinventing are especially wasteful considering the typically incremental nature of progress.
- Scientific rigor is compromised. Peer review is supposed to provide a measure of independent validation. Without access to the source code, it is impossible for referees to validate computational claims, or to determine whether the data used provided representative results. Computational results are a product of both theoretical and implementation efficiency, but there is little space available in print to discuss implementation innovations necessary for reproducing reported performance.
- Models and implementations are prone to loss. Because implementations and models are not written for public consumption and archived, they are easily lost. The community currently has no mechanism for capturing software genius for others to learn from and build on.
- Collaboration is inhibited by lack of standards. The lack of established venues for disseminating software contributes to the absence of software standards. (Even the standard MPS file format is interpreted differently by different commercial solvers.) Algorithms are often implemented using an application programming interface (API) to a commercial product. This binds the implementation to that product and impedes collaboration between colleagues who do not have access to the same product.
The Open-Source Alternative
What is open source? When one "buys software," one actually purchases a license from the copyright holder to use the software product. Today, the buyer usually receives a precompiled library or executable program, but not the source code. This allows the buyer to exercise the program but little else. Without source code, the buyer cannot fix a bug (or even pay someone else to fix it), nor can he modify or improve the software. Until recently, this proprietary model of software development and sales was commonly thought to be the only way complex pieces of software could be developed and made profitable. Open source has proved to be a valid alternative model. [2]
The term "open source" refers to a category of software licenses defined and promoted by a nonprofit corporation called the Open Source Initiative (OSI, http://www.opensource.org). To protect the term from misuse, the OSI runs a certification program. Software with the "OSI Certified" label is distributed under a license satisfying the Open Source Definition. Much broader than simply requiring access to source code, the Open Source Definition addresses the following fundamental issues: 1) free redistribution of source code, 2) accessibility of source code, 3) derived works, 4) integrity of the author's source code, 5) no discrimination against persons or groups, 6) no discrimination against fields of endeavor, 7) distribution of license, 8) license must not be specific to a product, and 9) license must not contaminate other software.
All the various OSI-certified licenses have certain attributes in common. Open-source licenses give users access to source code and the legal right to modify and redistribute the modifications so that the code evolves. Unlike software in the public domain, open-source software is clearly copyrighted. Open-source software differs from shareware or freeware, which are often only distributed as binaries. Unlike "free for academic use only" licenses, open-source licenses do not discriminate so that diversity and participation are maximized.
Open-source licenses can have significant differences. For example, distributed modifications can be taken private (e.g., the Berkeley System Distribution License) or must remain open (e.g., the GNU Public License). Open source is not anti-profit. It just promotes a different business model. One only need to look as far as the nearest bottled water to see that successful business can be built on goods which are also available at no cost. [3]
How does open-source development work? In a typical successful open-source software project (e.g., Linux), a volunteer army of users becomes a virtual community of developers. Users download the source code from the Web, and may use it as is or modify it for their own purposes. Users may find and fix bugs, extend functionality, and port to new platforms. Then they contribute their modifications to be incorporated into the base code distribution. Because of the relatively large number of developers, the code evolves rapidly.
The virtual community shares a set of values and has a pyramid structure. At the bottom are the many casual users, in the middle are developers, and at the top is a small core team that controls the changes to the official code distribution of the project. The core team may make decisions by consensus or majority rule, and may be led by a "benevolent dictator" with ultimate authority. Open-source communities are sometimes described as "brutal meritocracies"; they run on ego and reputation. Developers are volunteers who take pride in their work. The software does not have owners, but rather maintainers. Bugs are made public, not hidden.
This model of open-source development can produce high-performance, high-quality, reliable, secure code. Much of the Internet is run on open source. (Roughly 60 percent of Web sites run on the open-source Apache HTTP server, vs. 25 percent for Microsoft's IIS. [4]) But open source is not a panacea. Designing code so that it can be more easily modified and extended takes effort, as does writing code to be read and understood independently by others. Code must be documented to a higher standard, and conventions must be followed. Although reading and understanding a complex piece of code to the point where one can modify it takes effort and time, it will be far less costly to reuse a well-constructed open-source code than to rebuild the code from scratch.
What software should be open sourced? While open source addresses some of the current inhibitors to progress, it is unreasonable to expect all OR software to be opened. For instance, it is unlikely that software with significant potential for profit will be opened. On the other hand, software that has great technical or scientific value but is not central to a company's business, is a good candidate, as is software developed at universities in the course of research. To explore the merits and viability of open source in OR, COIN-OR was conceived.
What is COIN-OR? The Common Optimization INterface for Operations Research (COIN-OR) is an initiative to advance open source for the operations research community. The motivation is to increase the use of optimization by speeding the deployment of existing optimization techniques and accelerating progress in the research community. The public initiative was spearheaded by IBM Research and kicked off with a conference presentation, the first organizational meeting, and the launching of the project's Web site at the 17th International Symposium for Mathematical Programming in August 2000.
The software repository on the COIN-OR Web site was seeded with two state-of-the-art projects opened by IBM Research under the OSI-certified IBM Public License (IPL) and with two newly initiated projects. The four initial contributions featured tools for large-scale mixed-integer linear programming and combinatorial optimization. These tools, which continue to evolve today, are:
- Open Solver Interface is an API, written in C++ , that enables implementations to be "solver agnostic." Algorithms can be implemented once and then run using any solver having an open solver interface instantiation with no additional effort. Currently, interfaces to three commercial solvers (CPLEX, OSL, XPRESS-MP) and one subgradient solver (Volume Algorithm) are available in the repository.
- Branch-Cut-Price framework is a framework written in C++ for solving mixed-integer programs in parallel on a distributed network of workstations using LP-relaxation-based branch, cut, and price techniques. The BCP framework liberates users from having to code the backbone of functionality that is common to all branch, cut and price techniques so that they can more quickly develop and deploy their own problem-specific applications. BCP has been used by IBM Research in successful customer engagements, including projects in the airline and steel industries. BCP is now fully integrated with the open solver interface.
- The Volume Algorithm is an extended subgradient method that produces approximate primal solutions as well as the usual dual solutions. More generally, the Volume Algorithm can be used as a C++ framework for Lagrangian relaxation. The Volume Algorithm code is an implementation of patented technology that has been deployed in practice by IBM Research to solve large-scale scheduling problems arising in the airline industry. Although the algorithm itself is patented, this individual implementation is released under the IPL, which grants users a royalty-free patent license.
- The Cut Generation Library is a collection of cutting plane implementations, currently including a variety of knapsack-cover cuts, simple rounding cuts and odd-hole cuts.
- Derivative Free Optimization is a package for general nonlinear optimization problems where the objective function is relatively expensive to compute and the derivatives are not available and cannot be estimated efficiently.
- Open Tabu Search is a framework for tabu search methods written in Java and opened under the OSI-certified Common Public License.
The first cluster on open source at an INFORMS national meeting will be held this November in Miami Beach. This invited cluster includes two sessions covering a variety of research projects involving open code, a panel of leading OR software providers debating new directions and standards for the MPS file format, and a workshop on open-source tools for parallel branch, cut and price. For more information on the subjects and speakers, visit the online program at http://www.informs.org/Conf/Miami2001.
References
- R. Lougee-Heimer, "The COIN-OR Initiative: open source software for optimization", Proceedings of CP-AI-OR '01, pgs. 307-319.
- Eric S. Raymond, "The Cathedral and the Bazaar," http://www.tuxedo.org/~esr/writings/cathedral-bazaar/hacker-history.
- Robert F. Young, "Giving It Away: How Red Hat Software Stumbled Across a New Economic Model and Helped Improve an Industry," Open Source: voices from the revolution, O'Reilly & Associates, 1999.
- Netcraft, http://www.netcraft.com, July 2001.
- Matthew J. Saltzman, "COIN-OR: An Open-Source Library for Optimization," in Soren S. Nielsen (ed.), "Programming Languages and Systems in Computational Economics and Finance," Kluwer, Boston, forthcoming.
Contributors to this article:
Robin Lougee-Heimer
(IBM Research, robinlh@us.ibm.com)
Francisco Barahona
(IBM Research, barahona@us.ibm.com)
Brenda Dietrich
(IBM Research, dietric@us.ibm.com)
J.P. Fasano
(IBM Research, jpfasano@us.ibm.com)
John Forrest
(IBM Research, jjforre@us.ibm.com)
Robert Harder
(United States Air Force, Robert.Harder@pentagon.af.mil)
Laszlo Ladanyi
(IBM Research, ladanyi@us.ibm.com)
Tobias Pfender
(Konrad-Zuse-Zentrum fuer Informationstechnik Berlin, pfender@zib.de)
Theodore Ralphs
(Lehigh University, tkralphs@lehigh.edu)
Matthew Saltzman
(Clemson University, mjs@ces.clemson.edu)
Katya Scheinberg
(IBM Research, katyas@us.ibm.com)
OR/MS Today copyright © 2001 by the Institute for Operations Research and the Management Sciences. All rights reserved.
Lionheart Publishing, Inc.
506 Roswell Street, Suite 220, Marietta, GA 30060, USA
Phone: 770-431-0867 | Fax: 770-432-6969
E-mail: lpi@lionhrtpub.com
URL: http://www.lionhrtpub.com
Web Site © Copyright 2001 by Lionheart Publishing, Inc. All rights reserved.