Global Optimization Test Problems

Global Search, As Timely As Ever

``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

Test Problems for Unconstrained (or Bound Constrained) Optimization

Test Problems for Constraint Satisfaction

Test Problems for Constrained Optimization

Test Problems for Combinatorial Optimization

Test Problems for Other Optimization Problems

Real Life Test Problems from Space Mission Design

Test Problems

Many but not all of these problems have several local minima, but any reasonable global optimization algorithms should be able to cope with unique minimizers, too, without a huge overhead over local techniques. (One would like to have automatic stopping rules that can do this without cutting things off too early for multiple minima problems!)

A recent Handbook of Test Problems in Local and Global Optimization by C. Floudas et al. contains a large collection of test problems for local and global optimization problems of types including

multi-quadratic programming, bilinear and biconvex, generalized geometric programming, general constrained nonlinear optimization, bilevel optimization, complementarity, semidefinite programming, mixed-integer nonlinear optimization, combinatorial optimization, and optimal control problems, from application areas including

pooling/blending operations, heat exchanger network synthesis, phase and chemical reaction equilibrium, robust stability analysis, batch plant design under uncertainty, chemical reactor network synthesis, parameter estimation and data reconcilliation, conformational problems in clusters of atoms and molecules, pump network synthesis, trim loss minimization, homogeneous azeotropic separation system, dynamic optimization problems in parameter estimation and reactor network synthesis, and optimal control problems. Unfortunately, the book contains many misprints and mistakes. The algebraic test problems are available in the GAMS modeling language and the differential-algebraic problems are supplied in the MINOPT modeling language. All test problems can be downloaded from the above web site. (Hopefully, the problems are coded correctly.)

for unconstrained (or bound constrained) optimization

For low-dimensional problems, the standard test set in the local optimization community is

ACM Trans. Math. Software

optionally together with the bounds from

Numerical Analysis

Interesting Properties of Moré/Garbow/Hillstrom Test Functions (multiple minima, nearly flat plateaus, regions where roundoff matters, etc.)

Fortran Code for Moré/Garbow/Hillstrom test problems and gradients, and for some others

MATLAB Code for Moré/Garbow/Hillstrom test problems [Matlab code is also included in the source code for SolvOpt.] Note that in wood.m, J(3,3) has the wrong sign (minus sign is correct)!

Minimum Function Values and Gay's Bounds for Moré/Garbow/Hillstrom test problems

For large scale problems in local unconstrained optimization, the standard is the collection of
MINPACK-2 Test Problems for Large-Scale Optimization; the actual code for the problems is in tprobs*

Data Fitting Test Problems (by Klaus Schittkowski)

L.C.W. Dixon and G.P. Szegö, The global optimization problem: an introduction, pp. 1-15 in: in L.C.W. Dixon and G.P. Szegö (eds.), Towards Global Optimisation 2, North-Holland, Amsterdam 1978.

Matlab code

Cambridge Cluster Database (The Lennard-Jones cluster problem and more realistic cluster problems)

Pictures of Lennard-Jones clusters

Test Functions and Benchmarks for Genetic Algorithms (collected by Leo Lazauskas)
Of course, other global optimization algorithms should be able to solve these, too, and also be able to compete on the global optimization test set developed for the First International Contest on Evolutionary Optimization. It contains five problems, each in a 5- and 10-dimensional version.
Test Problems from the Second International Contest on Evolutionary Optimization (includes also one constrained example, with nonempty interior)
Since the above links are no longer working, here is code for ICEO1 and ICEO2 tests: iceo.tar.gz(C and Matlab, 16K) iceo.zip(C code only, 12K) and the global optima for ICEO1: iceo.txt

Test problem generator with known minimizers

Simple Challenges for Global Optimization Codes exhibiting features missing from many of the global optimization test problems in vogue

Shepard Interpolation Functions

A difficult exponential fitting problem

Test problems from R. Iwaarden's thesis

PGAPack set of test problems in Fortran and C,

Pictures of Some Test Functions (view same pictures in the US)

More Pictures (ps, 147K)

Test Functions for Evolutionary Algorithms (William M. Spears)

Test Problem Generators for Evolutionary Algorithms

for constraint satisfaction

Problems in this category have a set of equality or inequality constraints; at least one point (or all points) must be found that satisfies all constraints, or it must be decided that no such point exists.

The Moré/Garbow/Hillstrom test problems are standard test problems for the case of continuous variables when only one solution is requested. For testing the case where all solutions are wanted, this test set is probably too easy.

Test Database of Polynomial Systems (by Jan Verschelde)

Polynomial test suite (by D. Bini and B. Mourrain)

The COPRIN examples page for systems of equations and inequalities

The following links generally address the case of discrete variables.

Constraint Satisfaction Benchmarks, a list of links

14 Binary Constraint Satisfaction Programs in C with four test problem classes (graph coloring, n-queens, totally random, random with a solution)

NIST regression test problems

TESTNONLIN - Nonlinear Equation Tests in Fortran 90

for constrained optimization

The COCONUT Benchmark - A benchmark for global optimization and constraint satisfaction

constrained global optimization testproblems in GAMS format

Handbook of Test Problems in Local and Global Optimization By C.A. Floudas et al., Kluwer, Dordrecht 1999.

misprints and mistakes

The test problems are part of the GLOBAL Library of global optimization test problems coded as GAMS models.

The traditional test set for constrained local optimization is that by Hock and Schittkowski. It was designed for testing (low-dimensional) local optimization algorithms, but many of these test problems are nonconvex and possess several local minima with different objective function values. There is a Fortran 77 implementation of the collection.

A huge collection of (often large-scale) test problems is the CUTEst suite of Fortran subroutines, scripts and test problems for linear and nonlinear optimization, including a Matlab interface

The Hock/Schittkowski problems and part of the CUTEst problems are also part of the collection of Nonlinear Optimization Models in AMPL (collected by Bob Vanderbei)
with many additional problems from practical applications.

Mittelmann's collection of AMPL problems

COPS: Large-Scale Nonlinearly Constrained Optimization Problems (in AMPL and C)
Another, more recent test set is the COPS test results

The GAMS Model Library Index
nonlinear programming problems from practical applications, coded in GAMS

COMPleib, Constraint Matrix-Optimization Problem Library
a collection of test examples for nonlinear semidefinite programs, control system design and related problems

Nonlinear programming test function suite (for evolutionary computation)

The COPRIN examples page

Constrained Real-Parameter Optimization, CEC-06

QPlib2014, Quadratic Programming Library
A library of test problems for constrained optimization problems where the objective function and all constraints are linear or quadratic. (but no LPs)

The Ph.D. thesis of Tom Epperly contains problem definitions and solutions (ps.gz, 59K) for constrained global optimization problems together with test results for his branch and bound algorithm.

Concave Minimization Test Problems (Jacobsen and Moshirvaziri)
``All of the problems have non-global local minima.''

A Constrained Problem by Andy Keane

A constrained problem difficult for genetic algorithms ((Quanshi Xia)

ELIB list of test data for mathematical programming

MCPLIB (nonlinear mixed complementarity problems)

Test Problem Generators

A problem by Andy Keane with active constraints (with C code)

SDPLIB (semidefinite programming test problems)

OR-Library Nonlinear Programming Test Problems [currently empty, Jan 9 1997]

Netlib Linear Programming Test Problems (These are of course convex, but are included for the sake of completeness) and a Matlab version

Some of the online papers by Baker Kearfott contain constrained global optimization problems together with test results for his branch and bound algorithm.

The nonlinear programming FAQ contains a list of papers with optimization test problems. The papers are not online, however.

There is also a book,

A collection of test problems for constrained global optimization algorithms

for other continuous optimization problems

MPEC Library

for combinatorial optimization

The traditional test set for combinatorial optimization is the

MIPLIB

SOFTLIB

CSPLIB, a problem library for constraints

XML representation of CSP instances

DIMACS Challenge on Cliques, Coloring and Satisfiability (hard combinatorial optimization problems)

OR-Library test problems for quadratic assignment, etc.

QAPLIB (Quadratic Assignment Problem Library)

Benchmarks for Independent Set, Vertex Cover, Clique and Vertex Coloring(by Ke Xu)

Donald Knuth's Stanford GraphBase: A Platform for Combinatorial Computing (read abstract.plaintex first)

Generating Traveling Salesman Problems with known solutions

Exact Ground States of Spin Glasses

LOLIB library of sample instances for the linear ordering problem

sac-94-suite of 0/1 integer programming problems (by J. Heitkoetter)
(multiple knapsack problems)

A hard mixed integer problem (by D. Bienstock), with approx. 400 continuous variables and 56 (0,1)-variables

QBFlib, The Quantified Boolean Formulas Satisfiability Library

Planning & Scheduling Benchmarks: Resource Constrained Project Scheduling

planning and scheduling benchmark

Staff Rostering Benchmark Data Sets

Scheduling Benchmarks

Vehicle routing instances

VRPTW benchmark problems (routing and scheduling)

Planning & Scheduling Benchmarks (B.R. Fox and M. Ringer)

MINLP Library for mixed integer nonlinear programming problems

Test Problems for Mixed Integer Nonlinear Programming in AMPL or SIF

for other optimization problems

Performance Assessment of Multi-Objective Optimization Algorithms @ CEC-07

Stochastic Programming Problems (Robert Entriken)

Comparing Solution Methods for Dynamic Equilibrium Economies (S.B. Aruoba et al.)

Multidisciplinary Optimization Test Suite (Natalia Alexandrov)

Optimization Software and Test Problems (an extensive list of links by Tomomi Matsui)

Real Life Test Problems from Space Mission Design

25 difficult global optimisation problems related to spaceraft interplanetary trajectory optimisation

Test Results

The page with links to test results is beginning to grow. Please submit test results for your own algorithms (or any of the above ones) on any of the above test sets. The idea is that you can enter a competition on the fastest algorithms and you can look up the results others obtained with their favorite methods.

I'd like to encourage a common format for reporting results and invite your ideas about what you would like to see in a result database. To get you started, look at my current ideal for Test Result Presentation.

You might also be interested in my suggestions for a global optimization contest and in Benchmarking Optimization Software with COPS (by Jorge Moré's group at Argonne)