• Accelerate the development and deployment of O.R. technology.
  
  
• Maintain an open-source repository of O.R. software, models and data - available to all free of charge and on-demand.
  
  
• Provide a forum for the distribution and peer review of O.R. software.
  
  
• Nurture the development and maintenance of technical standards.
  
  
• Foster collaboration within the O.R. community.
  
  
• Promote the use of O.R.

In 2000, IBM Research announced its three-year commitment to host COIN-OR as an experiment to determine the potential of open-source software development in the O.R. community. The COIN-OR Web site debuted with four state-of-the-art research projects for optimization from IBM, the participation of one university and a call to the greater O.R. community for users, contributors, thought-provokers and leaders. This call was answered. Over the past four years COIN-OR has roughly tripled in size as new projects and contributions to existing projects have been made by a variety of individuals from universities, research labs, businesses and government. As of September 2004, COIN-OR contained a dozen projects totaling 170K lines of code and half a dozen mailing lists.

The COIN-OR Foundation


A major milestone towards COIN-OR's goal of becoming an independent, self-supporting entity run by the O.R. community was reached in March 2004. Four individuals from four universities in the U.S. and Canada — Lou Hafer (Simon Fraser University), Brady Hunsaker (University of Pittsburgh), Matthew Saltzman (Clemson University) and Ted Ralphs (Lehigh University) — created the COIN-OR Foundation, Inc., a non-profit educational foundation incorporated in the state of Maryland. The COIN-OR Foundation was incorporated to take over operation of the initiative from IBM Research.

The COIN-OR Foundation's management is structured into two boards: the Strategic Leadership Board (SLB) and the Technical Leadership Council (TLC). The SLB oversees business operations and sets the long-term agenda for the foundation. Its membership is balanced between representatives from industry and academia and includes advisory members from outside the foundation's membership. The SLB will hold its first meeting in October 2004 at the INFORMS Annual Meeting in Denver. The TLC oversees the foundation's technical operations and serves at the pleasure of the SLB. It guides the foundation's technical agenda, setting technical standards and broad technical goals. Its membership is balanced between developers and users of COIN-OR, as well as among technical disciplines. More details on the COIN-OR Foundation can be found on the incorporation Web site at www.math.clemson.edu/~mjs/coin-incorporated.html.

New Host: INFORMS Online


In conjunction with INFORMS Annual Meeting in October 2004, the COIN-OR Foundation will officially take over the project from IBM Research, and INFORMS Online will become COIN-OR's new host. The COIN-OR Foundation's existing suite of projects are briefly described on the following page.

• Branch-Cut-Price Framework, a parallel branch cut-price framework,
  
  
• Cut Generation Library, a collection of algorithms to generate cutting planes,
  
  
• COIN LP, a linear program solver,
  
  
• Derivative-Free Optimization, a package for solving general non-linear optimization problems when derivatives are unavailable,
  
  
• IPOPT, an interior point algorithm for general large-scale non-linear optimization,
  
  
• Multifario, a continuation method for computing implicitly defined manifolds,
  
  
• Non-Linear Program Application Programming Interface, subroutine interface for defining and solving non-linear programming problems,
  
  
• Open Solver Interface, a uniform subroutine interface for callable solver libraries,
  
  
• Open Tabu Search, a framework for creating tabu search algorithms,
  
  
• Simple Branch and Bound, a framework for creating branch and cut algorithms,
  
  
• Stochastic Modeling Interface, for optimization under uncertainty, and
  
  
• Volume Algorithm, a generalization of the subgradient method, which produces approximate primal solutions as well as dual solutions.

The volunteers who contribute to the foundation and the development of its projects are constantly striving to improve overall quality, documentation, ease of use and robustness. However, the level of success in achieving these goals varies by project depending on the support it receives from the community. The projects above reflect the interests of the individuals who have participated to date. The foundation's leadership hopes that new projects will be added that reflect the broad interests and needs of the O.R. community. Resources for visualization, data mining, simulation, constraint programming, statistics, forecasting, spreadsheets and more are welcome.

New Developments


Many people have contributed to the growing resources available under COIN-OR. To illustrate the variety of people and institutions involved (and at the almost-certain risk of inadvertent omissions), below are highlights of new technical developments in 2004.

In the COIN LP Solver:

• Version 1.0 is declared by John Forrest (IBM).
  
  
• The linear simplex code is no longer beta according to John's standards, thanks in part to feedback from Matthew Galati (SAS Institute, Inc.), Francois Margot (Carnegie Mellon University), Edwin Straver (Frontline Systems, Inc.) and Jean-Sebastien Roy (Research and Development Division, Electricité de France).
  
  
• The C interface to COIN LP Solver — enriched by Bob Entriken (Electric Power Research Institute) and Richard Waltz (Northwestern University). An interior point algorithm for models with linear or convex quadratic objectives — contributed by John Forrest.
  
  
• A sequential LP algorithm for non-linear objectives — contributed by John Forrest.
  
  
• A beta version of a quadratic simplex code — contributed by John Forrest.
  
  
• Sensitivity analysis — contributed by John Forrest.
  
  
• The COIN LP Solver is available on NEOS — thanks to Jeff Linderoth (Lehigh University).

In the Simple Branch and Bound:

• Local Branching based on the work of Andrea Lodi — contributed by John Forrest.
  
  
• C interface to Simple Branch and Bound — contributed by Bob Entriken.
  
  
• Simple Branch and Bound is available on NEOS — thanks to Jeff Linderoth.

In the Cut Generation Library:

• Flow cover cuts — contributed by Yan Xu (SAS Institute, Inc.), Jeff Linderoth and Martin Savelsbergh (Georgia Institute of Technology). Mixed-Integer Rounding Cuts — contributed by Joao Goncalves (Lehigh University) and Laszlo Ladanyi (IBM).
  
  
• "Two-step" Mixed Integer Rounding Cuts — contributed by Sanjeeb Dash (IBM), Marcos Goycoolea (Georgia Institute of Technology) and Oktay Gunluk (IBM). See the COIN-OR FAQs for links to a paper on the theory underlying this new class of cutting planes for general mixed-integer programs.
  
  
• Odd-hole cuts — contributed by Marta Eso (Hotchkiss School) and Laszlo Ladanyi.

In the Open Solver Interface:

• FortMP Open Solver Interface — contributed by Patrick Valente (Brunel University). Mosek Open Solver Interface — contributed by Bo Jensen (Mosek, Inc.).
  
  
• Upgrade of the Gnu LP Kit (GLPK) Open Solver Interface to use the latest GLPK API — contributed by Joseph Young (Sandia National Laboratories).
  
  
• Upgrade of XPRESS-MP Open Solver Interface — contributed by Oliver Bastert (Dash Optimization, Inc.).

In IPOPT:

• A beta version of a complete C++ re-write of IPOPT — contributed by Carl Laird (CMU) and Andreas Waechter (IBM). The new object-oriented design allows (i) more flexible interfacing to optimization problem model and linear algebra routines, and (ii) easier changes and augmentation of the optimization algorithm.

In Non-Linear Program Application Programming Interface:

• Support for IPOPT has been added — contributed by Michael Henderson (IBM) and Andreas Waechter.

In Stochastic Modeling Interface:

• A stochastic modeling interface for multi-period linear stochastic programs with recourse was released in October 2003, and new functions have been added throughout 2004, including a Stochastic MPS file reader and support for discrete distributions. The main interface, the SmiScnModel class, accepts any Open Solver Interface compatible solver for solution of the deterministic equivalent linear program. The COIN/Example directory contains a variety of samples illustrating various features — contributed by Alan King (IBM) and Christian CondevauxLanloy (University of Geneva).

In the Abstract Library for Parallel Search:

• The Abstract Library for Parallel Search is a new framework for implementing parallel search algorithms. Version 0.5 will be debuted on COIN OR in October — developed by Yan Xu, Ted Ralphs, Laszlo Ladanyi and Matthew Saltzman.

In SYMPHONY:

• SYMPHONY is a customizable framework for solving mixed-integer linear programs either sequentially or in parallel. SYMPHONY will be incorporated into COIN-OR in October. For more information, see www.branchandcut.org/SYMPHONY — developed by Ted Ralphs and Laszlo Ladanyi.

The resources at www.coin-or.org are available on demand, free of cost, under a license that does not distinguish between fields of endeavors. This makes it easy for O.R. professionals to collaborate with people everywhere, regardless of their employer.

Interested? At the annual meeting of INFORMS in Denver, come to the INFORMS Online reception in honor of the move, Sunday night, Oct. 24; attend the COIN-OR users meeting Monday, Oct. 25 at lunch; or drop by the COIN-OR booth in the Exhibit Hall anytime. The COIN-OR Foundation is powered by volunteers. Its scope and quality is limited only by who participates. We welcome your input.



Robin Lougee-Heimer of IBM Research, Matthew Saltzman of Clemson University and Ted Ralphs of Lehigh University developed this article on behalf of the COIN-OR community.

Table of Contents

OR/MS Today Home Page


OR/MS Today copyright © 2004 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 2004 by Lionheart Publishing, Inc. All rights reserved.