This CRAN task view contains a list of packages which offer
facilities for solving optimization problems.
Although every regression model in statistics solves an optimization
problem they are not part of this view. If you are looking for regression
methods, the following views will contain useful starting points:
Multivariate,
SocialSciences,
Robust
among others.
The focus of this task view is on
Optimization Infrastructure Packages
,
General Purpose Continuous
Solvers
,
Mathematical
Programming Solvers
and
Specific
Applications in Optimization
. Packages are categorized in these
three sections.
Many packages provide functionality for more than one
of the subjects listed at the end of this task view. E.g., mixed
integer linear programming solvers typically offer standard linear
programming
routines like the simplex algorithm. Therefore following each package
description a list of abbreviations describes the typical features
of the optimizer (i.e., the problems which can be solved). The
full names of the abbreviations given in square brackets can be
found at the end of this task view under
Classification According to
Subject
.
If you think that some package is missing from the list, please
let me know.

Trying to unify optimization algorithms via a single wrapper
function,
optimx
helps to proper specify the
(nonlinear) optimization problem including objective function,
gradient function, and scaling. This package supports the
(local) optimization of smooth, nonlinear functions with at most
box constraints (bounds).
optimx
depends not only on
packages and/or functions mentioned in this section of this task
view but also on two packages implemented by the author(s),
namely
Rcgmin
and
Rvmmin. Both are "pure
R" implementations of conjugate gradient minimization and
variable metric nonlinear function minimization algorithms,
respectively.

The R Optimization Infrastructure (ROI) package
provides a framework for handling optimization problems in R. It
uses an object oriented approach to define and solve various
optimization tasks in R which can be from different problem
classes (e.g., linear, quadratic, nonlinear programming
problems). This makes optimization transparent for the R user as
the corresponding workflow is completely abstracted from the
underlying solver. Furthermore, this approach allows for easy
switching between solvers, given that corresponding solver plugins
are available, and thus enhances comparability.

Package stats offers several general purpose optimization
routines.
First, function
optim()
provides an implementation of
the BroydenFletcherGoldfarbShanno (BFGS) method,
bounded BFGS, conjugate gradient, NelderMead, and simulated
annealing (SANN) optimization
methods. It utilizes gradients, if provided, for faster
convergence. Typically it is used for unconstrained optimization
but includes an option for boxconstrained
optimization.
Additionally, for minimizing a function subject to
linear inequality constraints stats contains the routine
constrOptim().
For onedimensional unconstrained function optimization there is
optimize()
which searches an interval
for a minimum or maximum.
Then there is
nlm
which is used for solving nonlinear
unconstrained minimization problems. Eventually,
nlminb()
offers unconstrained and constrained
optimization using PORT routines. [RGA, QN]

Implementations of the augmented lagrange multiplier method
for general nonlinear optimization can be found in
packages
alabama
and
Rsolnp.

clue
contains the function
sumt()
for
solving constrained optimization problems via the sequential
unconstrained minimization technique (SUMT).

Package
cmaes
implements a global optimization
procedure using a covariance matrix adapting evolutionary
strategy (CMAES).

Package
dfoptim, derivativefree optimization
procedures, contains quite efficient R implementations of the
NelderMead and HookeJeeves algorithms (unconstrained and
boundsconstrained). [DF]

GenSA
is a package providing a function for
generalized simulated annealing which can be used to search for a
global minimum of a very complex nonlinear objective function
with a very large number of optima.

Package
gsl
provides BFGS, conjugate gradient,
steepest descent, and NelderMead algorithms. It uses a "line
search" approach via the function
multimin(). It is
based on the GNU Scientific Library (GSL). [RGA, QN]

Package
maxLik
provides a general purpose
NewtonRaphson optimizer
maxNR()
as well as wrapper
to methods, implemented in
optim(). It supports fitting a
submodel by specifying constant parameters.

An R port of the Scilab neldermead module is packaged
in
neldermead
offering several direct search
optimization algorithms based on the simplex method.

Package
nloptr
provides access to NLopt, an LGPL
licensed library of various nonlinear optimization algorithms. It
especially supports global optimization with routines such as
DIRECT, StoGo, and others. It includes local derivativefree
(COBYLA, NelderMead, Subplex) and gradientbased (e.g., BFGS)
methods, and also the augmented Lagrangian approach. [DF, GO, QN]

Several derivativefree optimization algorithms are provided
with package
minqa. E.g., the
functions
bobyqa(),
newuoa(),
and
uobyqa()
allow to minimize a function of many
variables by a trust region method that forms quadratic models by
interpolation.
bobyqa()
additionally permits box
constraints (bounds) on the parameters. [DF]

Package
powell
optimizes functions using Powell's
UObyQA algorithm (Unconstrained Optimization by Quadratic
Approximation).

A particle swarm optimizer (PSO) is implemented in package
pso. The algorithm follows the standard PSO 2007 by
Maurice Clerc et al. Additionally, a number of ancillary routines
are provided for easy testing and graphics. Another (parallelized)
implementation of the PSO algorithm can be found in package ppso
available from
rforge.net
.

subplex
provides unconstrained function
optimization based on a subspace searching simplex method.

Package
ucminf
implements an algorithm of
quasiNewtonian type for nonlinear unconstrained
optimization. [QN]

In package
trust, a routine with the same name offers
local optimization based on the "trust region" approach.

Package
nleqslv
provides a
function
nleqslv()
implementing Newton and Broyden
methods with line search and trust region global strategies for
solving medium sized system of nonlinear equations.

In package
gafit
gafit()
uses a
genetic algorithm approach to find
the minimum of a onedimensional function.

Package
genalg
contains
rbga(), an implementation of a genetic algorithm for
multidimensional function optimization.

Machine coded genetic algorithm (MCGA) provided by package
mcga
is a tool which solves optimization problems based
on byte representation of variables.

Package
rgenoud
offers
genoud(), a routine which is capable of solving
complex function minimization/maximization problems by combining
evolutionary algorithms with
a derivativebased (quasiNewtonian) approach.

An R implementation of the SelfOrganising Migrating Algorithm
(SOMA) is available in package
soma. The approach of
this stochastic optimization algorithm is similar to that of
genetic algorithms and can be applied to any costminimization
problem with a bounded parameter space, and is robust to local
minima.

Package
DEoptim
provides a global optimizer based
on the differential evolution algorithm.
RcppDE
provides a C++ implementation of the
DEoptim()
function.
This section provides an overview of open source as well as commercial
optimizers. Which type of mathematical programming problem can be solved
by a certain package or function can be seen from the abbreviations in
square brackets. For a
classification by subject
see
the list at the end of this task view.

Package
linprog
solves linear programming problems using
the function
solveLP()
(the solver is based on
lpSolve) and can read model files in MPS
format. [LP]

In package
quadprog
solve.QP()
solves
quadratic programming problems
with linear equality and inequality constraints. [QP]

BB
contains the function
spg()
providing a
spectral projected gradient method for large scale optimization with
simple constraints. It takes a nonlinear objective function as an
argument as well as basic constraints. Furthermore,
BB
contains two functions (
dfsane()
and
sane()) for using the spectral gradient method
for solving a nonlinear system of equations.

In the
boot
package there is a routine called
simplex()
which realizes the twophase tableau simplex
method for (relatively small) linear programming problems. [LP]

kernlab
contains the function
ipop
for
solving quadratic programming problems using interior point
methods. [IPM, QP]

limSolve
offers to solve linear or quadratic
optimization functions. [LP, QP]

LowRankQP
primal/dual interior point method solving
quadratic programming problems [IPM, QP]

Package
rcdd
offers the function
lpcdd()
for solving linear programs with exact arithmetic using the
GNU Multiple Precision (GMP)
library. [LP]

In package Rdonlp2 (see the
rmetrics
project)
function
donlp2(), a wrapper for the DONLP2
solver, offers the minimization of smooth nonlinear functions and
constraints. DONLP2 can be used freely for any kind of research
purposes, otherwise it requires licensing. [GO, NLP]

The
NEOS Server
for Optimization
provides online access to stateoftheart
optimization problem solvers. Package
rneos
enables the
user to pass optimization problems to NEOS and retrieve results
within R.

An interface to Ipopt from the
COINOR
initiative called
ipoptr
is available from
RForge
. Ipopt is an open
source solver for largescale nonlinear continuous
optimization. [NLP]
Interfaces to Open Source Optimizers

Package
clpAPI
provides high level access from R to
lowlevel API routines of the
COIN OR Clp
solver
library. [LP]

Package
lpSolve
contains the routine
lp()
to solve LPs and MILPs by calling the freely
available solver
lp_solve
. This solver is
based on the revised simplex method and a branchandbound (B&B)
approach. It supports semicontinuous variables and Special Ordered
Sets (SOS). Furthermore
lp.assign()
and
lp.transport()
are aimed at solving assignment problems
and transportation problems, respectively. Additionally, there is the
package
lpSolveAPI
which provides an R interface to the
low level API routines of lp_solve (see also project
lpsolve
on
RForge
).
lpSolveAPI
supports reading linear programs from files in lp
and MPS format. [BP, IP, LP, MILP, SPLP]

Packages
glpkAPI
as well as
package
Rglpk
provide an interface to the
GNU Linear Programming
Kit
(GLPK). Whereas the former provides high level access
to low level routines the latter offers a high level routine
Rglpk_solve_LP()
to solve MILPs using GLPK. Both
packages offer the possibility to use models formulated in the MPS
format. [BP, IP, IPM, LP, MILP]

Rsymphony
provides the routine
Rsymphony_solve_LP()
which
interfaces the SYMPHONY solver for mixed integer linear
programs. SYMPHONY applies LP
relaxation with a branchandcut approach. It is part of the
Computational
Infrastructure for Operations Research
(COINOR) project which is an initiative to spur the
development of open source software for the operations research
community. [LP, IP, MILP]

The CSDP semidefinite programming library is interfaced by
package
Rcsdp. [SDP]
Interfaces to Commercial Optimizers
This section surveys interfaces to commercial solvers. Typically, the
corresponding libraries have to be installed separately.

Packages
cplexAPI
and
Rcplex
provide an
interface to the CPLEX solver package from
IBM
. CPLEX
provides dual/primal simplex optimizers as well as a barrier
optimizer for solving large scale linear and quadratic
programs. Furthermore, it offers a mixed integer optimizer to
solve difficult mixed integer programs. Note that CPLEX is
not
free
and you have to get a license from
IBM
. Academics will receive a free
licence upon request. [LP, IP, BP, QP, MILP, MIQP, IPM]

Package
Rmosek
offers an interface to the
commercial optimizer from
MOSEK
. It provides dual/primal
simplex optimizers as well as a barrier optimizer. In addition to
solving LP and QP problems this solver can handle second order
cone programming (SOCP) and quadratically constrained programming
(QPQC) tasks. Furthermore, it offers a mixed integer optimizer to
solve difficult mixed integer programs (MILP, MISOCP, etc.). Note
that you have to get a license from
MOSEK
. Academic licenses are free
of charge. [LP, IP, BP, QP, MILP, MIQP, IPM]

In package
clue
solve_LSAP()
enables
the user to solve the linear
sum assignment problem (LSAP) using an efficient C implementation of
the Hungarian algorithm. [SPLP]

The data cloning algorithm is a global optimization approach
and a variant of simulated annealing which has been implemented
in package
dclone. The package provides low level
functions for implementing maximum likelihood estimating
procedures for complex models using data cloning and Bayesian
Markov chain Monte Carlo methods.

Package
goalprog
provides some functions for
lexicographic linear goal
programming and optimization. Goal programming is a branch of
multiobjective, multicriteria decision analysis. [MOP]

igraph, a package for graph and network analysis,
uses the very fast igraph C library. It can be used to calculate
shortest paths, maximal network flows, minimum
spanning trees, etc. [GRAPH]

Package
minpack.lm
provides an interface to the
LevenbergMarquardt nonlinear leastsquares algorithm found in
MINPACK.

maxLik
adds a likelihoodspecific layer on top of
a number of maximization routines like BrendtHallHallHausman
(BHHH) and NewtonRaphson
among others. It includes summary and print methods which
extract the standard errors based on the Hessian matrix and allows easy
swapping of maximization algorithms.

Multicriteria optimization problems can be solved using
package
mco
which implements genetic
algorithms. [MOP]

Package
optmatch
provides routines for solving
matching problems by translating
them into minimumcost flow problems, which are in turn solved
optimally by the RELAXIV codes
of Bertsekas and Tseng (free for research). [SPLP]

Package
quantreg
contains variations of simplex and
of interior point routines (
nlrq(),
crq()). It provides an interface to L1 regression
in the R code of function
rq(). [SPLP, LP, IPM]

Package
sna
contains the function
lab.optim()
which is the frontend to a series of heuristic routines for optimizing
some bivariate graph statistic. [GRAPH]

Package
TSP
provides basic infrastructure for
handling and solving the
traveling salesperson problem (TSP). The main routine
solve_TSP()
solves the TSP
through several heuristics. In addition, it provides an interface
to the
Concorde TSP
Solver
, which has to be
downloaded separately. [SPLP]
What follows is an attempt to provide a bysubject overview of
packages.
The full name of the subject as well as the corresponding
MSC
code (if available) are
given in brackets.

LP (Linear programming, 90C05):
boot,
clpAPI,
cplexAPI,
glpkAPI,
limSolve,
linprog,
limSolve,
linprog,
lpSolve,
lpSolveAPI,
rcdd,
Rcplex,
Rglpk,
Rsymphony,
quantreg

GO (Global Optimization):
nloptr

SPLP (Special problems of linear programming like transportation,
multiindex, etc., 90C08):
clue,
lpSolve,
lpSolveAPI,
optmatch,
quantreg,
TSP

BP (Boolean programming, 90C09):
cplexAPI,
glpkAPI,
Rglpk,
lpSolve,
lpSolveAPI,
Rcplex

IP (Integer programming, 90C10):
cplexAPI,
glpkAPI
lpSolve,
lpSolveAPI,
Rcplex,
Rglpk,
Rsymphony

MIP (Mixed integer programming and its variants MILP for LP
and MIQP for QP, 90C11):
cplexAPI,
glpkAPI,
lpSolve,
lpSolveAPI,
Rcplex,
Rglpk,
Rsymphony

SP (Stochastic programming, 90C15):
stoprog

QP (Quadratic programming, 90C20):
cplexAPI,
kernlab,
limSolve,
LowRankQP,
quadprog,
Rcplex

SDP (Semidefinite programming, 90C22):
Rcsdp

MOP (Multiobjective and goal programming, 90C29):
goalprog,
mco

NLP (Nonlinear programming,
90C30): Rdonlp2,
Rsolnp

GRAPH (Programming involving graphs or networks, 90C35):
igraph,
sna

IPM (Interiorpoint methods, 90C51):
cplexAPI,
kernlab,
glpkAPI,
LowRankQP,
quantreg,
Rcplex

RGA (Methods of reduced gradient type, 90C52): stats
(
optim()),
gsl

QN (Methods of quasiNewton type, 90C53): stats
(
optim()),
gsl,
nloptr,
ucminf

DF (Derivativefree methods, 90C56):
dfoptim,
minqa,
nloptr