In 2006, a major effort led by the Technical Leadership Council of the COIN-OR Foundation was undertaken to standardize the COIN-OR infrastructure and improve the ease-of-use for users and developers across projects. Improvements include:

* One project-management system. Every project on COIN-OR now uses Trac, an enhanced "wiki" [a novel mechanism that allows any user to freely and simply edit a Web page's content] and issue tracking system for software development projects. From a project's Trac Web page, any user can add information to the site, browse the source code, report problems by submitting a "ticket" and more.

* One version-control system. Every project on COIN-OR now uses Subversion, a "version control system" that manages multiple revisions to the same software. All projects using the less flexible CVS version control system have been migrated. The standardization and advanced features of Subversion mean more convenience for users and developers.

With the move to Subversion, a new numbering system for stable versions and release versions of COIN-OR projects was begun. The new numbering system will facilitate bug reporting, managing dependencies of one project on another and systematically releasing binaries.

* Better build systems. COIN-OR now uses GNU autotools, the de-facto standard for building applications across Unix-like platforms. For projects that have adopted autotools, a user can build the project with a simple sequence of commands (configure, make, make install). The build system automatically determines the available compilers and external libraries, and the appropriate default options. For Windows users, project files for Microsoft Visual Studio Version 7 and 8, in addition to Version 6, are now available.

* Binary distributions. COIN-OR now distributes binaries. The binary distribution system enables users satisfied with the major releases of the main COIN-OR packages to download pre-compiled packages for their platforms, including all required libraries. This feature is currently available for Windows, Linux and MacOS X.

New Projects


Six new projects debuted on COIN-OR in 2006:

* Bonmin by Larry Biegler, Pierre Bonami, Gerard Cornuejols, Ignacio Grossman, Carl Laird, Francois Margot and Nick Sawaya (CMU) with Andrew Conn, Jon Lee, Andrea Lodi and Andreas Waechter (IBM). Bonmin (Basic Open-source Nonlinear Mixed INteger programming) is an experimental open-source C++ code for solving or finding good solutions to mixed integer nonlinear programs. Bonmin uses other COIN-OR packages as building blocks: CBC, CLP, CGL, OSI and Ipopt. It comes with an interface to be used from AMPL, and can be called from C++ code. Bonmin is one of the results of a collaboration that took place during the last two years between researchers at Carnegie Mellon University and IBM. Although still experimental, Bonmin has been tested on a relatively large library of problems.

* coinMP by Bjarni Kristjansson (Maximal Software). coinMP is a Windows dynamic linked library (DLL) that supports most of the functionality of COIN-OR LP, COIN-OR Branch-and-Cut and Cut Generation Library projects. The coinMP distribution of the COIN-OR projects for Windows offers these advantages: high portability, does not require any compilation, easy to use and can be used from any other Windows application.

* CSDP by Brian Borchers (New Mexico Tech). CSDP is a library of routines that implements a predictor corrector variant of the semidefinite programming algorithm of Helmberg, Rendl, Vanderbei and Wolkowicz. The main advantages of this code is that it is written to be used as a callable subroutine, it is written in C for efficiency, and it makes effective use of sparsity in the constraint matrices. CSDP has been compiled on many different systems. The code should work on any system with an ANSI C Compiler and BLAS/LAPACK libraries.

* FlopC++ by Tim Hultberg (EUMETSAT). FLOPC++ is an algebraic modeling language embedded in C++. The goals of FLOPC++ are: to be as robust, efficient and easy to use, for linear optimization, as, traditional algebraic modeling languages, such as AMPL and GAMS; to facilitate the integration of optimization models in software applications; to facilitate the efficient implementation of model-tailored solution algorithms; and to remain lightweight.

* KSP by Mary Helander (IBM). The goal of this project is to share implementations of published k-shortest path algorithms, which are often building blocks of practical OR applications in transportation, vehicle routing, facility location, telecommunication network design, social network analyses, and other areas. The seed contribution includes a C implementation of the k-shortest path algorithm published by Miaou and Chin in 1991.

* SVM-QP by Katya Scheinberg (IBM). SVM-QP (Support Vector Machines Quadratic Programming solver) is a software package that solves the 2-norm soft margin support vector machine classification problem, where the problem is formulated as a convex quadratic program. SVM-QP is designed for large-scale problems. The underlying algorithm is an active set method for convex QPs. The currently available implementation is written in Fortran 77, and is designed to trade memory for efficiency. Currently, this is the most time-efficient version of SVM-QP. A somewhat slower memory-saving version is under development.

Established Projects Evolve


Established projects continued to evolve thanks to many people in the user and developer communities. At the almost-certain risk of inadvertent omissions, below are highlights of developments in 2006.

In the COIN-OR Branch and Cut (CBC) and the COIN-OR Linear Program Solver (COIN LP):
* Both CLP and CBC are more reliable and faster than in 2005. The capability to exploit SOS2 constraints has been significantly improved. Major functionality changes have been made to support the development of mixed-integer nonlinear program solvers (e.g., Bonmin). Mixed-integer nonlinear programming continues to be the focus area, and technology used to find a proven optimal solution for the trimlon12 problem will be appearing in CBC to allow for even more use of the library by the mixed-integer nonlinear community.

In the Cut Generation Library (CGL):
* A new lift-and-project cut generator, CglLandP, was contributed by Pierre Bonami. There are now 16 different cut generators available for use in teaching, research and business, with more in the pipeline.

* CGL is now co-managed; Francois Margot joined Robin Lougee-Heimer as a project manager of CGL.

In CppAD:
* CppAD is being successfully used by the System for Population Kinetics (SPK, https://spk.rfpk.washington.edu/info/) to differentiate user-defined models. SPK is sponsored by the National Institute of Biomedical Imaging and Bioengineering at the National Institutes of Health.

In Derivative-Free Optimization (DFO):
* DFO is being successfully used in oil reservoir simulation models by a major South American oil company.

In IPOPT:
* An option to approximate second derivatives using the L-BFGS quasi-Newton update was added to the C++ version (3.*) of IPOPT. While such an approximation was available in the previous Fortran version (2.*), the new implementation aims to achieve more robust and efficient performance. In particular, the approximation can be performed in the subspace of the nonlinear variables only.

* At the core of each IPOPT iteration lies the solution of a sparse symmetric indefinite linear system, which usually occupies most of the computation time. Interfaces to several linear solvers have been added, which allow a user to possibly improve performance by using a linear solver that works better for particular applications. Most of those new interfaces have been contributed by members of the OS community: MA57 (Michael Hagemann), Pardiso (Olaf Schenk), MUMPS (Damien Hocking). Also an interface for WSMP was added.

* A simple derivative checker has been incorporated, which allows users to verify easily whether the derivative information implemented in their code seems to be correct.

In Volume Algorithm:
* The Volume Algorithm and other COIN-OR components were used by Francisco Barahona and Laszlo Ladanyi (IBM) in "Branch and Cut Based on the Volume Algorithm: Steiner Trees in Graphs and Max-Cut," RAIRO Operations Research 40 (2006) 53-73.

Other Developments


* Jason Sarich (Argonne National Lab) and Jeff Linderoth (Lehigh University) wrote interfaces for three NEOS solvers (Bonmin, CBC and IPOPT) to work automatically within AMPL via the NEOS-Kestrel Interface, neos.mcs.anl.gov/neos/ kestrel.html. For a complete list of COIN-OR software available through NEOS, see www.coin-or.org/download.html.

* Junction Solutions (www.junctionsolutions.com) is successfully using COIN-OR software. Junction Solutions is the largest provider of vertical industry-focused enterprise software and services based on the Microsoft Dynamics(tm) AX. As part of their Food and Beverage offering, Junction Solutions uses FlopC++, CBC, CLP, along with proprietary supporting libraries. In their next release, they plan to expand their use of COIN-OR within the Food and Beverage offering, and across other offerings.

* Eudoxus Systems (www.eudoxus.com) is the latest corporate sponsor of COIN-OR. Eudoxus Systems, based in the United Kingdom, develops computer-based solutions to hard business problems by applying advanced mathematical techniques based on mathematical programming. For more on how your company can support COIN-OR's mission, contact info@coin-or.org.

* COIN-OR has a new logo, thanks to Seprian Damayanto (tsepriand@yahoo.com). Seprian's design was selected from more than 65 submissions by the COIN-OR Foundation membership. The submissions were made to a logo contest organized for the COIN-OR Foundation by Kevin Furman (Exxon Mobil Research & Engineering), Brady Hunsaker (University of Pittsburgh) and Robin Lougee-Heimer (IBM).

* The Center for Discrete Mathematics and Theoretical Computer Science (DIMACS) held its first workshop on COIN-OR. The four-day workshop drew 75 registrants, representing 11 companies, two government agencies and 21 universities from U.S., Canada, Europe and South America. The workshop was sponsored by DIMACS and IBM and organized by Jonathan Eckstein (Rutgers), Jeff Linderoth, Robin Lougee-Heimer and Francois Margot.

* COIN-OR exhibited for the first time at a EURO meeting, thanks to the generosity of the EURO XXI 2006 organizing committee. A user meeting, tutorial and six presentations were held at the conference in Reykjavik, Iceland.

* At the INFORMS annual meeting in Pittsburgh, an invited cluster was co-sponsored by ICS on open-source software. The 13-session cluster highlighted a broad range of open-source efforts in O.R. and the work of many people in the COIN-OR community. A booth in the exhibit area was made possible thanks to the generosity of INFORMS.

* The COIN-OR Foundation and the INFORMS Computing Society (ICS) formed a strategic partnership in 2006 to further their mutual goals. ICS has been a strong supporter of COIN-OR since its beginning in 2000, co-sponsoring conference tracks and sessions. The partnership is a natural development, according to John Chinneck, chair of the ICS: "The core concern of ICS is the interface between computing and operations research, and this is exactly where the COIN-OR project exists," he said. "It's no surprise that many of the COIN-OR officers are also ICS members. As a society we are very enthusiastic about this partnership and the benefits that it will bring to our members."

Need code? Got code? Get involved. By making your resources (data, models, source code, interfaces, etc.) available to the community at COIN-OR, you can receive recognition, tap into potential collaborators and establish a foundation for others to build on. (See www.coin-or.org/contributions.html for details on how to submit code to COIN-OR.) By using the resources at COIN-OR and providing feedback on your experience (e.g., usability, quality, needed functionality), you can get better tools.



Robin Lougee-Heimer is a research staff member with the Mathematical Sciences Department at the IBM TJ Watson Research Center in Yorktown Heights, N.Y., and one of the creators of the COIN-OR initiative.

Table of Contents

OR/MS Today Home Page


OR/MS Today copyright © 2007 by the Institute for Operations Research and the Management Sciences. All rights reserved.


Lionheart Publishing, Inc.
506 Roswell Rd., 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 2007 by Lionheart Publishing, Inc. All rights reserved.