``Consider
everything.
Keep the
good.
Avoid evil
whenever you notice it.''
(1 Thess. 5:21-22)
This file is part of my global optimization web site. It contains sections on
We are working on a comparative evaluation of a number of currently available constrained global optimization programs. The results will be made publicly available here. If, as an authors of such software, you are interested in our evaluation of your code, the notes on Global Optimization Software Evaluation will tell you what you need to know.
Janos Pintér's recent Optima Newsletter survey on continuous global optimization software is now available online. Please send new or updated information regarding your global optimization software to Janos Pintér.
Below is a list of publicly available global optimization programs (and a few commercial ones). The quality in terms of speed, reliability, and/or automatic parameter choices, stopping tests and ease of use differs widely. I have not checked out the codes (will perhaps be done some day); but I am very interested in comparisons (cf. test results available online) or any other useful comments (mail here) on the sources given.
In a few cases, I added information on problems where a code has difficulties. This is not meant to criticize the code (it may work excellent on other classes of problems) but as a service to the research community: to challenge researchers to overcome current limitations, and to compete for better and better techniques.
Lack of critical information doesn't mean that a code has no problems, but only that nobody informed me about any weaknesses. Indeed, all current global optimization codes for nonlinear problems are unreliable (i.e., cannot always find the global optimum in a reasonable, predictable amount of time and space), with unknown performance limits.
At the present stage of knowledge, if you need global optimization you must experiment with the known methods (or packages) until you have something satisfying you. Unfortunately, this is a rather unsatisfactory state of the art... In general, performance must be expected to deteriorate with increasing dimension. Dimension 50-100 is probably already very high for general-purpose codes on all but the simplest problems. Many codes allow no constraints or only bound constraints.
Since I was asked repeatedly what to try first, here are some suggestions for continuous problems. But they are backed up by little else than my feelings of what I'd try first, and I am using a small font size to emphasize that this is information of a poorer quality than in the rest of my pages. Please write me if you have significant experience that leads to improved suggestions, or that confirms the ones given.
A list of global optimization codes in the public domain (or at least free for academic users). Please respect the author's conditions for using and/or modifying the codes.
interalg, interval global solver for nonlinear programming (in Python, by Dmitrey Kroshko)
BMIBNB, Global solver for nonconvex problems in the YALMIP modeling environment (in Matlab, by Johan Löfberg)
ICOS, rigorous complete solver for continuous constraint satisfaction problems
LaGO, Branch and Cut algorithm for nonconvex mixed integer nonlinear programs
RSOLVER (by Stefan Ratschan)
for solving quantified inequality constraints. Examples include:
projecting the solution set of a set of inequality constraints to two
dimensions.
GANSO, programming library for global and non-smooth optimization with linear constraints (with both complete and probabilistic methods, free for up to 20 variables and up to 20 constraints)
Concave, concave programming with linear constraints (by Alexander Rusakov)
LP_SOLVE, Sparse Mixed Integer Linear Programming
(by Michel Berkelaar), a
Matlab Interface
(by Kantor and Chen; get lpmex.tar and lpmex_ext.tar), and an
Online Interface (by Dmitry Golovashkin)
LINDO, LINGO for linear and nonlinear mixed integer programs (small-scale versions available for free)
Visual XPRESS Linear mixed integer programming (free student edition, for models with at most 100 rows and 200 variables, and tables and variables having at most two dimensions)
MODLER integer linear programming in DOS (by Harvey Greenberg)
ABACUS, A Branch-And-Cut System
for combinatorial and linear mixed integer optimization
(by Stefan Thienel)
(calls the commercial Cplex or SoPlex packages)
Mixed Integer LP-optimizer (Borland Pascal, by Markus Weidenauer)
setconst, NLP solver with set constrained variables in Matlab
(assumes that a solver for the NLP with set constraints replaced by
bound constraints is available)
NLBranch, Mixed Integer Nonlinear Programming Solver
(seems to assume that for fixed discrete parameters, the problem is
convex)
cGOP, Global Optimization Program in C
(by Visweswaran and Floudas)
Solves global optimization problems with an objective function of the
form
a^Tx+b^Ty+x^TAy+f_1(x)+f_2(y) with convex f_1, f_2,
and linear constraints. [Any linearly constrained problem with objective
function of the form `quadratic+convex' can be brought into this form by
introducing additional variables.]
Requires the commercial codes MINOS 5.4 and (or?) CPLEX 3.0 to solve
subproblems.
``cGOP has been in use at the Computer-Aided Systems Laboratory in
Princeton University for the last two years, and has been used to
solve problems involving several hundred variables and constraints.
Currently, versions are available for Hewlett-Packard, Silicon
Graphics and IBM RS6000 machine architectures.''
BOB: Branch-and-bound Optimization liBrary (for combinatorial optimization)
INTOPT_90 Interval Branch and Bound ands its sequel
GlobSol in Fortran 90 (by Baker Kearfott)
for global optimization with general factorable constraints, with
rigorously guaranteed results (even roundoff is accounted for
correctly)
Parallel version (with MPI, by Chenyi Hu)
Reduced Space Branch and Bound in C++ (by Tom Epperly)
for global optimization with general factorable constraints
[link dead]
PROFIL/BIAS Interval Branch and Bound (by Jansson and Knüppel)
bound constrained global optimization, with rigorously guaranteed
results (even roundoff is accounted for correctly)
C-code for PC and a number of UNIX platforms, because of machine
dependence in the interval arithmetic
The code has problems for certain rational objective functions (such as
Wood, Kowalik-Osborne, Bard from the
Moré/Garbow/Hillstrom test set),
where the natural interval
extension results in excessive overestimation
Concave programming (by Alexander Rusakov)
Q01SUBS (by Panos Pardalos)
minimizes sparse quadratic functions subject to {0,1}-constraints.
Concave quadratic problems with finite two-sided bound constraints can
be rephrased in this way.
Portable Parallel Branch-and-Bound Library (by Stefan Tschoeke)
BOB, Parallel Branch-and-bound Optimization Library
RSOLVER (by Stefan Ratschan)
for solving quantified inequality constraints. Examples include:
projecting the solution set of a set of inequality constraints to two
dimensions.
QEPCAD, Quantifier Elimination by Partial Cylindrical Algebraic Decomposition (mathematically rigorous)
INTSOLVER: An interval based solver for Global Optimization (in Matlab, by T. Montanher)
INTBIS (by Baker Kearfott)
finds all solutions of polynomial systems of equations, with rigorously
guaranteed results (even roundoff is accounted for correctly)
IAsolver in Java (Brandeis Interval Arithmetic Constraint Solver)
zerOne vertex enumeration code for 0/1 polytopes
OPBDP, implicit enumeration for 0-1 problems in C++
(by Peter Barth)
Logic-Based 0-1 Constraint Programming
clp(FD), Constraint Logic Programming over Finite Domains
CUTSDP Toolbox for a Cutting-Plane Approach Based on Semidefinite Programming, with three applications: max-cut, graph bisection, and graph equipartition (by Stefan Karisch)
VBCTOOL Visualization of Branch and Cut algorithms
GloptiPoly (in Matlab, by Henrion and Lasserre)
globally ''minimizing a multivariable polynomial function subject to
polynomial inequality, equality or integer constraints.''
A related recent Matlab 6 program is
SOSTOOLS for sums of squares optimization problems.
Global Minima of Polynomial Optimization Problems using Gröbner Bases (by Kristoffer Hägglöf)
CMPSm, Continuation Method for Polynomial Systems
(in Matlab)
for finding all isolated solutions of a system of polynomial equations
Black Box Optimization with Data Analysis for the global optimization of smooth problems with expensive objective and/or constraints (by Kevin Kofler)
MCS, Multilevel Coordinate Search a Matlab program for bound constrained global optimization using function values only (by Huyer and Neumaier)
NLopt algorithms for derivative-free global optimization
Jörg Gablonsky's Fortran implementation of DIRECT, Divide Rectangles, a simple global optimization method for bound constrained problems by Jones, Perttunen and Stuckmann
Direct.m, a Matlab implementation of DIRECT
14 Binary Constraint Satisfaction Programs in C
(by Peter van Beek)
The recommended method is FC_CBJ (= number 11).
ECLiPSe, a development environment for constraint programming applications
TOMS/647 Quasirandom Sequence Generator (29K, in Fortran 77) with low discrepancy for deterministic global search in dimensions 1-40
TOMS/738 Niederreiter's Low Discrepancy Sequences (127K, in Fortran 77) for deterministic global search in arbitrary dimensions
Complementarity Toolbox for MATLAB (by Mike Ferris)
Inductive Search Algorithm
in C++ (by George Bilchev)
Very fast, but may fail occasionally. Got the first place at the
1st International Contest on Evolutionary Computation
on a real-valued function testsuite.
Solution of integer systems of linear equations in Fortran (by J. Springer)
0-1 Multiple Knapsack Problem in Fortran (by Martello and Toth)
CGU, Convex Global Underestimation Code for protein folding (by Andy Phillips)
Global Optimization Using Hyperbolic Cross Points (by Novak and Ritter)
CSA, constrained simulated annealing with AMPL interface
SIMMAN, Simulated Annealing Code in Fortran
(37K, by Bill Goffe)
from netlib; handles bound constraints
ASA, CalTech Adaptive Simulated Annealing Code in C
(by Lester Ingber) and a
Matlab Interface
handles bound constraints
EBSA, Ensemble Based Simulated Annealing in C (by Richard Frost)
SA, Simulated Annealing Code in C++, C, Ada and Forth (by Everett Carter)
Differential Search Algorithm (DSA) for unconstrained optimization (by Pinar Civicioglu)
PSwarm, global optimization for bound constrained and linearly
constrained problems
with interfaces to AMPL, Python, R
CMA-ES, Covariance Matrix Adaptation Evolution Strategy
for bound constrained optimization (by Nikolaus Hansen)
Best code in the 2005 IEEE Congress on Evolutionary Computation
Benchmark (with code for the comparison)
Constrained differential evolution
for constained nonlinear programming (by Tetsuyuki Takahama)
Best code in the 2006 IEEE Congress on Evolutionary Computation
Benchmark
GENOCOP III, Genetic Algorithm for Constrained Problems in C
(by Zbigniew Michalewicz)
GENOCOP III Code (60K)
handles general nonlinear constraints using quadratic penalty terms
DE, Differential Evolution Genetic Algorithm
(local copy, with an interface for sequential use)
for unconstrained problems, in Matlab and C (by Rainer Storn)
(The bounds to be provides only delineate the initial search region.)
DE has won the third place at the 1996
1st International Contest on Evolutionary Computation
on a real-valued function testsuite. DE was the best genetic algorithm
approach. (The first two places of the contest were won by non-GA
algorithms.)
Matlab Code for Biomimicry for Optimization
PIKAIA, genetic algorithm in Fortran77/90 (by Charbonneau,Knapp and Miller)
PGAPack, Parallel Genetic Algorithm in Fortran and C, with an extensive test set (from Argonne National Laboratory)
GAS, Genetic Algorithm in C++ (by Jelasity and Dombi)
GAOT, Genetic Algorithms Optimization Toolbox in Matlab (by Jeffrey A. Joines)
Genetic Algorithm in Matlab (by Michael B. Gordy)
GAucsd, Genetic Algorithm in C (from University of California, San Diego)
Genesys Genetic Algorithm in C (tar.Z, 708K, by John Grefenstette)
GAlib, C++ Genetic Algorithm Library (by Matthew Wall)
GAC Genetic Algorithm in C and Common Lisp (by Bill Spears)
GAGA Genetic Algorithm for General Application in C (by Ian Poole)
PARAGenesis Parallel Genetic Algorithm in C* (tar.Z, 121K, by Michael van Lent)
Evolutionary Algorithms for MATLAB (links by Hartmut Pohlheim)
Particle swarm and simulated annealing codes (by Brecht Donckels) [download links currently unaccessible]
BIPOP-CMAES, one of the best stochastic global solvers in 2009 (if enough function values are permitted)
space, Stochastic Process Analysis of Computer Experiments (bound constrained optimization of very expensive functions of few variables, in C++, by Matthias Schonlau)
Stochastic ranking for constrained evolutionary optimization (Matlab code by Runarsson and Yao)
GLOBAL, Derivative-Free Boender-Timmer-Rinnoy Kan Algorithm
in Fortran 77 and C (by Tibor Csendes)
Fortran 95 version (translated by Alan Miller)
StoGO, stochastic bound constrained global optimization using gradients (in C++)
The SGOPT Optimization Library (by William Hart)
``The SGOPT optimization library provides an object-oriented interface
to a variety of optimization algorithms, especially stochastic
optimization methods used for global optimization.... SGOPT includes a
generic C++ genetic algorithm facility that is similar to the GAlib
package. Additionally, it contains mechanisms for GA-local search
hybrids, as well as an implementation of evolutionary pattern search
algorithms.''
StoGO in C++ , branch and probability bound code for bound constrained problems, needs function values and gradients
IHR, Improving-Hit & Run Algorithm in Fortran
(by Zelda Zabinsky)
allows integer constraints and general inequality constraints (assuming
a strictly feasible point exists)
SPSA, Simultaneous Perturbation Stochastic Approximation (Matlab code for noisy global optimization, by James Spall)
TOMS/744, Stochastic algorithm for global minimization with constraints in Lisp (by F. M. Rabinowitz)
TOMS/667 in Fortran77
(210K, by Aluffi-Pentini, Parisi and Zirilli)
global optimization via stochastic integration;
with Fortran code of low-dimensional global optimization test problems
Bayesian Global Optimization in Fortran and C++ (by Audris Mockus)
Level Set Programming for Global Optimization (zip, 79K)
(
Austrian Mirror Site)
Integer Local Search: WSAT(OIP)
LIONsolver, reactive search for
GRASP, Dense Quadratic Assignment Problems
GRASP, Quadratic Assignment and Set Covering Heuristics
QAPP, Quadratic Assignment Branch and Bound
Facility Layout and Location MATLAB Toolbox
(by Michael G. Kay)
includes a mixed integer LP solver (based on the Matlab optimization
toolbox)
BARON, Branch-And-Reduce Optimization Navigator
in Fortran (by Nikos Sahinidis)
A general purpose solver for optimization problems with nonlinear
constraints and/or integer variables. Fast specialized solvers for
many linearly constrained problems. GAMS interface.
LINDO/LINGO now has global optimization facilities
Interval Global Solver from Frontline Systems. Visual Basic and Excel interfaces
LSGRG Nonlinear Mixed Integer Solver for AMPL
MINOPT (Mixed Integer Nonlinear Programming)
GAMS/DICOPT Solver for Mixed Integer Nonlinear Programming
EZMod Quadratic Mixed Integer Programming (QMIP) Solver
CPLEX Linear Mixed Integer Solver (branch-and-bound for mixed integer linear programs)
CMMIP, Mixed Integer Programming for mixed integer LPs
``In CMMIP, each processor runs a version of CPLEX ... Parallelism is
attained by looking at multiple nodes of the branch-and-bound search
tree simultaneously ... near-linear speedups on up to 128 processors''
MINTO, Mixed INTeger Optimizer for mixed integer LPs
IBM Optimization Subroutine Library (OSL) (with a branch-and-bound mixed integer QP solver)
NAG FortMP (branch-and-bound mixed integer LP solver)
XPRESS-MP (mixed integer LP, QP and MINLP solver)
TOMLAB modeling and optimization environment. It includes, apart from many local algorithms, improved versions of the global optimization algorithms DIRECT and EGO of Jones, rbfSolve of Gutmann and Powell, Pinter's LGO, and mixed integer nonlinear solvers of Leyffer and Fletcher.
OptQuest (Tabu and Scatter search, etc.)
OptiREX, Cutting optimizer for rectangular sheets
ILOG Solver C++ software library which solves industrial problems for which generating or optimizing a solution is a highly combinatorial task, using constraint satisfaction techniques
Koalog Constraint Solver in Java
HEURO, Integrated Optimization Environment (for large scale black box global optimization with expensive objective function)
LGO, Lipschitz global optimization, an integrated development environment for global optimization problems with Lipschitz continuous objective and constraints (by Janos Pinter)
MathOptimizer for Mathematica
constrained local and global optimization
IOSO, Indirect Optimization Based on Self-Organization
in Fortran 77, for large-scale and possibly
multiobjective inequality constrained problems
heuristic: builds local statistical models from function values and
optimizes these
Constrained Global Optimization with Mathematica (including mixed integer problems and 0-1 integer problems) using adaptive grid refinement (by Loehle Enterprises, commercial)
Generator, Genetic Algorithm (for Excel worksheets)
``You can use Generator to maximize profits...''
(... of New Light Industries, Ltd., of course)
Magestic, Data Fitting by Global Optimization (for Excel worksheets, commercial)
GLO Global Local Optimizer
(by Michael J. Murphy)
genetic algorithm for expensive black box (finite element) objective
functions with constraints
Pointer, Constrained Optimization Tool with automatic selection or combination of up to four different search algorithms, including their tuning parameters (by Synaps, Inc.)
OptiA
``Options for global optimization include algorithms based on cluster
analysis and Monte Carlo techniques.''
Curvi for bound constrained optimization (by Windward Technologies)
OPTECH guided stochastic search for constrained global optimization
GEATbx Matlab Genetic and Evolutionary Algorithm Toolbox (by Hartmut Pohlheim)
Astrokettle Bin Packing in 2D and 3D
HIRON, stochastic global search for multivariate functions on a box
CLP(BNR), Constraint Logic Programming for Boolean, Natural and Real variables
ECLiPSe, ECRC Constraint Logic Parallel System constraint satisfaction (cheap for academic users)
IF/Prolog Prolog constraint satisfaction package
CHIP Prolog, C, and C++ programs for constraint satisfaction and scheduling
Constraint Logic Programming over Finite Domains in SICStus Prolog
Integer Programming Links from the Optimization Software Guide
Global (and Local) Optimization
Introduction to Global Optimization
Global Optimization Techniques
Global Optimization Software
Local Optimization Software
Optimization Test Problems
Global Optimization Test Results
People in Global (and Local) Optimization
Applications of Optimization
More Global (and Local) Optimization
Topics Related to Optimization
Mathematics Links
Statistics Links
Computational Mathematics Links
Mathematical Software
Interval Methods
Regularization
Protein Folding
my home page (http://www.mat.univie.ac.at/~neum)