1	COIN-OR: Open-source Software for Operations Research What, Why and How Brenda Dietrich Robin Lougee-Heimer
2	“What” COIN-OR is A repository of source code, models, data, examples Available for re-use Under open-source licenses Powered by volunteers
3	What is “Open Source”? A category of software licenses Rules by which code can be used, copied, modified, distributed,... Freely available, usually via Internet Changes typically given back A philosophy Healthy virtual community Debugs, maintains, enhances the source
4	Common “Open-Source” Misconceptions All open-source licenses are the same E.g., Viral vs. non-viral “Free for academic use only” is open source Discrimination Open source is the same as freeware/shareware Binary executable to end-user software Restricted intellectual property rights COIN-OR recommends the Common Public License OSI-certified open source license which permits IBM (and others) to share AND still use the code in commercial products.
5	Open Source in the Software Stack
6	“Why” for the community? Reuse rather than reinvent Fairer comparisons Build on the best Promote standards Foster collaboration and cross-pollination Outlet for software not “product destined”
7	“Why” for IBM ? Vehicle for IBM Research working with universities Alternatives Awards with no strings attached Employment as a “work for hire” Shared control enables true collaboration and invention Lessened IP issues Concept expanding to other areas of IBM interest
8	“Why” for IBM ? Vehicle for working with universities Alternatives Awards with no strings attached Employment as a “work for hire” Shared control enables true collaboration and invention Lessened IP issues Concept expanding to other areas of IBM interest
9	“How”? Companies Universities Individuals IBM
10	“How”? Companies such as…
11	“How”? Universities including… Brunel Carl von Ossietzky University, Oldenburg Carnegie Mellon Clemson Cornell Konrad-Zuse-Zentrum für Informationstechnik Berlin Lehigh Northwestern Politecnico di Milano Rutgers Simon Fraser University Universite de Geneve U of Arizona U of Pittsburgh U of São Paulo U of Washington U of Waterloo ….
12	Individuals
13	“How”? IBM External Consulting Yield Management for a railway Space allocation and payload balancing Service offerings Watson Implosion Tool (WIT) New version of EasyModeler Internal Consulting EinsTuner The design of every custom microprocessor developed by IBM uses nonlinear optimization software available on COIN-OR. Basic Research, e.g., Simultaneously branch and price Two Mixed Integer Rounding Cuts
14	Layered Solvers
15	Current Status COIN-OR Foundation, Inc Educational non-profit corporation Established 2004 Hosted by True community ownership Milestone accomplishment IBM is participating and supporting COIN-OR is more open IBM is not less interested
16	COIN-OR Projects
17	Frameworks
18	Abstract Library for Parallel Search (ALPS) A scalable, high-performance tree-search engine Improves on the simple master-worker scheme of BCP and SYMPHONY Supports general tree-search algorithms Integer Global optimization Constraint programming Frees developers from worrying about implementing the tree manager Parallel management Designed to support data-intensive problems Ted Ralphs, Project Manager
19	Branch-Cut-Price Library (BCP) Branch-Cut-Price Library Framework for creating custom LP-based branch-cut-price codes to solve Mixed Integer Programs (MIPs) Parallel management Any OSI-capable LP solver Any cuts from CGL Allows development of efficient problem class specific MIP algorithms with minimal implementation effort Laszlo Ladanyi, Project Manager
20	COIN-OR Branch & Cut (CBC) Branch and cut code to solve mixed-integer programs Designed to work with Any OSI-capable solver Any cuts from the CGL Flexibility Designed to be much more flexible than commercial codes Facilitates user written Branching strategies Node selection Heuristics Cutting planes John Forrest, Project Manger
21	SYMPHONY User interaction Black box solver for MILPs MPS files GMPL files FLOPC++ Callable library C API C++ API (OSI) Customizable framework C callback functions Execution modes Sequential Shared memory parallel Distributed memory parallel Additional functionality Multicriteria MILP solver Basic sensitivity analysis Warm starting Ted Ralphs, Project Manager
22	Open Tabu Search (OTS) A framework for Tabu Search Clean design and class structure Solution Tabu List Move Move Manger Objective Function Enables quick development Reactive search Learning search Self-expanding search Written in Java Can exploit multi-processor systems Can be embedded in Enterprise JavaBeans Framework Robert Harder, Project Manager
23	Interfaces
24	COIN-OR Open Solver Interface A uniform API for calling math programming solvers Supports functions such as Creating the LP formulation; Directly modifying the formulation by adding rows/columns; Modifying the formulation by adding cutting planes provided by CGL; Solving the formulation (and resolving after modifications); Extracting solution information; Invoking the underlying solver's branch-and-bound component. 11 OSI interfaces have been implemented CLP - John Forest CPLEX - Tobias Achterberg dylp - Lou Hafer FortMP – Patrick Valente GLPK - Brady Hunsaker MOSEK – Bo Jensen OSL - Laszlo Ladanyi SOPLEX – Tobias Achterberg SYMPHONY - Menal Guzelsoy VOL – Laszlo Ladanyi XPRESS-MP – Matthew Saltzman Matt Saltzman, Meta-project Manager
25	OSI CPLEX Solver Interface Author
26	COIN-OR NonLinear Programming API An API for defining and solving nonlinear programming (NLP) problems A set of C subroutines that create, modify and query in a data structure which represents the problem. Interfaces to LANCELOT and IPOPT are available Michael Henderson, Project Manager
27	COIN-OR Stochastic Modeling Interface Enables communication of stochastic data and solutions between modeling environments and solvers Alan King, Project Manager Christian Condevaux-Lanloy, key developer
28	Solvers
29	COIN-OR LP Solver (CLP) A high-quality open-source linear program solver Simplex Interior point Quadratic objective Extensible matrix format Pivot-level control John Forrest, Project Manger
30	Derivative Free Optimization (DFO) Solver for general nonlinear optimization problems with Small (<100) number of variables Expensive to evaluate functions Derivatives or their estimates not available Katya Scheinberg, Project Manager
31	DYLP Implementation of the Dynamic Simplex Algorithm Padberg, Linear Optimization and Extensions Research code Designed as a LP solver for use in an LP-based branch-cut-price MIP solver Flexibility over speed Copious trace output Extensive consistency checks Lou Hafer, Project Manager
32	Interior Point OPTimizer (IPOPT) An interior point algorithm for nonlinear, non-convex, constrained optimization problems Opened by CMU Andreas Waechter, Project Manager Carl Laird, C++ version
33	Volume Algorithm (VOL) A subgradient method that produces approximate primal as well as dual solutions Scales exceptionally well on large problems with combinatorial structure Primal solution comes from estimating the volumes below the faces of the dual problem. Small infeasibilities in the primal vector are negligible in many practical settings. The original subgradient algorithm produces only dual solutions. Francisco Barahona, Project Manager
34	Other Projects
35	COIN-OR Cut Generation Library A library of cutting plane generators Standardized format More than 11 cut available Cliques – Laszlo Ladanyi Duplicate Row – John Forrest Flow Cover – Yan Xu Gomory – John Forrest Knapsack Cover - Robin Lougee-Heimer Lift-and-project cuts using "norm 1" - Robin Lougee-Heimer Mixed-Integer Rounding – Joao Goncalves Odd Hole – John Forrest Probing – John Forrest Simple Rounding – Robin Lougee-Heimer Two mixed-integer rounding – Oktay Gunluk Robin Lougee-Heimer, Meta-project Manager
36	COIN-OR Utilities (Coin) Library of utilities used by multiple projects Laszlo Ladanyi, Project Manager
37	CppAD Given a C++ algorithm that computes function values, CppAD generates an algorithm that computes its derivative values The step by step conversion from an algorithm that computes function values to an algorithm that computes derivative values is Algorithmic Differentiation (often referred to as Automatic Differentiation) Brad Bell, Project Manager
38	Multifario A C library for finding solutions to nonlinear systems of equations with a small number of parameters. Uses user-supplied domain specific solver, to which Multifario presents a sequence of problems at carefully chosen parameter values. The resulting set of solutions covers the solution manifold in a specific part of parameter space. Interfaces to LOCA and AUTO packages Reference implementation of published algorithm Mike Henderson, Project Manager
39	Elsewhere Open-Source Lab at Oregon State University First of its kind at public university Cyberinfrastructure NSF Hardware, software, data testbeds Is a “service”, like the interstate A lot of people want to drive on the road, not many want to lay tar. Maintainable (pot holes! Road crews) Accessible (entrance ramps; mgt) Useable (road signs) Taxes? Tolls? Billboards? Examples NEOS COIN-OR
40	Challenges Documentation Ease of use Recognition Testing Intellectual Property Maintenance
41	Using COIN-OR www.coin-or.org Tarballs and CVS NEOS CLP CBC DFO IPOPT Products E.g, Frontline Systems and Knitro Support Free E.g, coin-discuss@list.coin-or.org Buy
42