A survey of free and open source optimization software

Optimization (also known as mathematical programming, or numerical optimization) includes

* Discrete and Integer Optimization

* Continuous Optimization (local max/min of a function of a real n-vector)

Decision tree for optimization problems and software links This site aims at helping you identify ready to use solutions for your optimization problem, or at least to find some way to build such a solution using work done by others.

Some open source software

All the packages listed below are currently active.

* COIN-OR (Common Public License)

The Computational Infrastructure for Operations Research (COIN-OR, or simply COIN) project is an initiative to spur the development of open-source software for the operations research community.

"Our goal is to create for mathematical software what the open literature is for mathematical theory."

COIN-OR is intended to host all types of OR software, eg, integer programming. A very active, large, well-organized software package with lots of developers.

A variety of projects are listed at the COIN-OR projects page. There are many projects. Here are a few:

* OpenOpt (license: BSD) A free numerical optimization framework for solving NLP, LP, MILP, QP, and other optimization problems. Very new project. Developed in Python and dependent on NumPy (Python's numerical package, BSD-licensed as well).

* CVXOPT (license: GLP3+) Source language: C, Python; API: Python. Included in Sage. (Possible legal issue: The CVXOPT distribution includes the source code of part of the SuiteSparse collection of sparse matrix algorithms. UMFPACK and the Supernodal module of CHOLMOD are licensed under the terms of the GNU General Public License, version 2 or higher.)

* CVXMOD (license: GPL3+) Builds on cvxopt. Python-based tool for expressing and solving convex optimization problems. It uses CVXOPT as its solver. It is developed by Jacob Mattingley, as PhD work under Stephen Boyd at Stanford University. Still in alpha stage.

* glpk (license: GPL3) GNU Linear Programming Kit, a solver a software package intended for solving large-scale linear programming, mixed integer programming, and other related problems. It is a set of routines written in ANSI C and organized in the form of a callable library.

* PyMathProg (license: GPL3) Python reincarnation of AMPL and GNU MathProg modeling language, implemented in pure Python, connecting to GLPK via PyGLPK. Create, optimize, report, change and re-optimize your model with Python, which offers numerous handy goodies.

* abacus (license: LGPL) ABACUS is a C++ framework for the implementation of branch-and-bound algorithms using linear programming relaxations. Cutting planes or columns can be generated dynamically (branch-and-cut, branch-and-price, branch-and-cut-and-price). Supports the Open Solver Interface (Osi) developed by the COIN-OR project which means that every solver supported by OSI can be used to solve the relaxations. Included is an example TSP solver.

* lp_solve (license: LGPL) lp_solve is a linear (integer) programming solver based on the revised simplex method and the Branch-and-bound method for the integers. lp_solve solves pure linear, (mixed) integer/binary, semi-continuous and special ordered sets models. lp_solve is not too big - less than 4M uncompressed.

* Zimpl (license: GPL) Mathematical modelling language with translation into a linear or (mixed-) integer mathematical program expressed in .lp or .mps file format which can be read and (hopefully) solved by a LP or MIP solver (like those from COIN-OR, or lp-solve).

References

* Wikipedia's list of optimization software

* Argonne Labs wiki on optimization

* A Sage example using CVXOPT by Josh Kantor

* branchandcut.org a community resource for researchers and those who want to learn more about branch, cut, and price algorithms, as well as a distribution point for open-source software implementing branch, cut, and price algorithms.

optimization (last edited 2009-08-01 12:57:29 by RobertSchwarz)