Problems/ Software

Benchmarks Testcases

Books/ Tutorials

Tools

Websub- mission

Other Sources

The Constrained NLO Problem The Problem: min f(x) subject to h(x)=0, g(x)>=0, n=dim(x), m=dim(g), p=dim(h). The picture shows feasible domain and level sets for f(x)=x1^2+x2^2, g(x)=(x1^2-x2,x2^2-x1) . Infeasible points are shown in dark brown and the levels of f are shown in the feasible domain. You'll find several sections: The LP-problem, also mixed integer and stochastic The QP-problem, also mixed integer Semidefinite and second-order cone programming Geometric programming The general nonlinear problem (dense, sparse, nonsmooth, SIP) Mixed integer nonlinear programming Network constraints Special/constraint solvers Control problems other collections/problems The LP-problem: f, g, h linear in x The LP-problem is often very high-dimensional. Several tools are necessary to deal with such problems. Some are listed here: plam A free MILP modeling environment using lp_solve as MILP solver and SWI-Prolog LPL Another free modeling language (Windows binaries only) for MILP MPS The description of the most widely used LP input format MPSreader An MPS reader for Windows lp2mps a utility (extracted from lp_solve) to convert the simple LP format to (and from) MPS ABACUS A general branch&cut library for mixed integer capability (no_s, C++, binaries for major platforms, requires SOPLEX, XPRESS-MP, or CPLEX as LP solver, has a simple TSP solver as demonstration example) The following simplex-based solvers allow some or all of the variables to be constrained to attain integer values; all allow input in MPS format: lp_solve C, procedural interface, Matlab interface, Java source of version 2.0, AMPL interface, Debian GNU Linux version, DOS executable Pascal-MILP-solver Borland-Pascal sources, DOS/OS2 binaries BonsaiG C, B&B, dynamic LP, partial arc consistency algorithm, binaries MOMIP no_s, B&B&cut, Win95 binary, binaries MINTO B&B, primal heuristics, allows to use problem specific knowledge, needs CPLEX or OSL (Solaris version) MOSEK Simplex/IPM, not PD, no_s, Matlab, AMPL, GAMS interfaces GLPK GNU LP library, B&B, dual/revised simplex, interior point, Concorde interface, C, Matlab interface, DOS executable SBB Simple branch&cut solver, part of COIN-OR (C++) MATLOG (MATLAB) The milp.m solver (needs lp.m from Matlab optimization toolbox) Further basic IP/MILP codes are available at SAL-ORLib Pure 0/1, IP solvers, mixed integer solver (Basic, f77, C, Pascal, Java) PURE LP SOLVERS: all allow input in MPS format: SOPLEX Simplex based, C++ BPMPD interior point method, Win95-version, Unix-binaries (version 2.21), netlib-source (version 2.11, f77), C-version (version 2.11, f2c), AMPL interface HOPDM local version of code (interior point method using predictor-corrector-steps of higher order), HOPDM_C (f2c-converted version, includes f2c-library), IIASA-archive (C++/f77, dynamic memory allocation, binaries for Solaris and win95 only) PCx interior point method, f77/C, binaries for major platforms LOQO interior point method, C, no_s, student binaries, executables for major platforms, work for two months w/o license, AMPL interface, Matlab interface COPL-LP

interior point method, no_s, includes crossover, DOS executable, HP binary, Linux binary
	LIPSOL	interior point method, also MAT or LPP formats, in Matlab-4/5 and f77
	IPO/SIMPO	interior and simplex LP-solver published in conjunction with Vanderbei's book, C
	PCLP	predictor-corrector interior point code, SciLab or Matlab
	LPABO, LPAKO, LPASO	interior point resp. simplex based solvers, LPASO includes crossover, no_s, Win, Linux, Solaris gcc-libs
	MINOS	the long standing simplex based REFERENCE-implementation, not PD, no_s
	MCMA	Multi-objective LP (Win95 and Solaris binaries only, includes tutorial models, based on HOPDM and MOMIP)

All accept input in SMPS format
	SMPS format reader	by Gus Gassman, in f90
	BNBS	A multistage stochastic linear programming code free for academic research. Requires an LP solver (CPLEX or SOPLEX or GLPK)
	MSLiP	A Multistage Stochastic Linear Programming Code, available for research and teaching purposes from Horand I. Gassmann
	SLP-IOR	based on GAMS, large solver library, free for academic use
	IBM OSL Stochastic Extensions	for multistage problems, free academic license

The QP problem: f quadratic, (non)convex, g, h linear

Only bound constraints:

	gpcg	More&Toraldo's method combining cg with gradient projection
	gpcg_c	f2c converted version of gpcg, includes f2c-lib
	BoxQP	package by H.B. Nielsen et al (f77, paper)
	MINQ	General definite and bound constrained indefinite quadratic programming (in Matlab)

Only equality constraints ( m = 0):

toms/559

also for nonconvex f, provided the projected Hessian is positive definite

n not too large, m >= 0, p >= 0:

	dualqp	f77 version of Spellucci's Goldfarb-Idnani dual QP solver
	dualqp_c	f2c converted version, includes f2c-lib
	IQP	indefinite QP
	SOLQP	indefinite QP solver, interior point based , in Matlab
	QLD f77, QLD C	QLD, Schittkowski's implementation of Powell's method

n large, m >= 0, p >= 0

	Extended MPS format	from BPMPD
	COPL_QP	interior point, C, ext. MPS input, user's guide
	BPMPD	extension of LP-code, ext. MPS input, Win-95 version Unix-binaries
	MOSEK	interior point, Win, Linux, Solaris binaries, ext. MPS input including quadratic constraints or through Matlab
	OOQP	object oriented C++ package, primal-dual interior point, needs MA27/57 from HSL archive
	GALAHAD	QPA/QPB active set and IPM solvers, AMPL and ext. MPS(SIF) input
	HOPDM	extension of LP-code, ext. MPS input
	QHOPDM	extension of HOPDM, ext. MPS input, matrix in quadratic term must be given as FTF
	LOQO	interior point method, C, no_s, executables for major platforms, work for several months w/o license, AMPL interface, Matlab5 interface
	RAL-QP	more QP codes (from the NA group at Rutherford Appleton Labs)

Mixed integer quadratic programming:

	MIQP	branch&bound code, nominal fee, contact S. Leyffer
	MOSEK	ext. MPS input, Win, Linux, Solaris binaries, Matlab, quadratic constraints

SDP&SOCP (semidefinite and second-order cone programming)

Cone World new initiative by GAMS

semidefinite programming (SDP) solvers

	SBmethod	C++ implementation of the spectral bundle method for minimizing the maximal eigenvalue of an affine matrix function (real, symmetric).
	SDPT3-2.3	Matlab implementation of infeasible path-following and homogeneous self-dual algorithms with Mehrotra type predictor-corrector and four types of search directions.
	DSDP	C-implementation of the Ye-Benson dual scaling algorithm, Matlab interface
	SDPHA	A Matlab package for a homogeneous primal-dual method
	CSDP	A library for semidefinite programming, predictor-corrector version of algorithm by Helmberg, Rendl, Vanderbei, and Wolkowicz (C)
	SDPA MPI-parallel version Matlab-version	Solves semidefinite programs utilizing a Mehrotra-type predictor-corrector step, uses sparse matrix structure, includes documentation (C++)
	PENNON	Penalty/barrier method for nonlinear and semidefinite programming, SDPA format input,
	SDPSOL	Solves c^Tx-log(detG(x)) subject to the linear matrix inequality constraints G(x)>0, F(x)>0, subsumes LP, QP, and other convex problems, includes the author's SP and MAXDET programs for which sources are available, no_s, binaries for major platforms, very convenient to use with Matlab
	CUTSDP	A Toolbox for a Cutting-Plane Approach Based on Semidefinite Programming (C)

SOCP solvers (second order cone problems, not SDP)

	MOSEK	Interior point code for LP, QP, and conic programming. Extended MPS or Matlab input, no_s
	SOCP	software for second order cone programming (C and Matlab)

SQL solvers (semidefinite, quadratic, linear problems, includes SDP, SOCP)

	SeDuMi	Matlab toolbox for solving optimization problems over symmetric cones, survey paper
	SDPT3-3.0	Matlab implementation of infeasible path-following algorithms with Mehrotra type predictor-corrector and two types of search directions.
	SDPpack	Primal-dual Mehrotra type predictor-corrector scheme, test for degeneracy and other additions, of historical interest

SDP solvers for discrete optimization problems

	COPL_SDP	solves various cut problems, uses dual scaling method(C)
	COPL_DSDP	mixed integer linear semidefinite problems, enhanced COPL_SDP, MPS-like input (C)
	Max-AO	solves SDP relaxations of maximum stable set and maximum clique problems, graph input (C)
	SDP-LR	solves SDP relaxations of the maximum cut, minimum bisection, and Lovasz theta problems, graph input (C)

Applications of SDP/SQL/SOCP

	LMILab Translator	Allows to use Matlab LMILab commands&format for Matlab-based SDP solvers
	SeDuMiInt	Interface to SeDuMi to solve and analyze linear matrix inequalities (GPL, Matlab)
	YALMIP	Matlab LMI parser with interfaces to most solvers listed here
	LMITOOL	Matlab LMI parser with an interface to SeDuMi
	Matrix completions	Using SDP to solve the PSD and the Euclidean distance matrix completion problems (Matlab)
	FIR toolbox	Matlab toolbox to optimize FIR filters and similar structures; needs SeDuMi or LOQO or other
	GloptiPoly	Polynomial objective and constraints, integer variables, needs SeDuMi (Matlab, GPL)
	SOSTOOLS	Matlab toolbox to solve sum of squares polynomial problems; needs SeDuMi and Matlab's symbolic toolbox (GPL)

Geometric programming

	MOSEK	Interior point method, Win, Linux, Solaris binaries, Matlab
	COPL_GP / binaries	Primal-dual interior point method, includes user's guide
	GPGLP	Self-extracting DOS archive, docs, examples

The general nonlinear Problem

Using function values only

The functions f, g, h are not necessarily smooth. Only function values required.

	COBYLA2 (f77, dble prec) COBYLA2_f90 COBYLA2_C (f2c converted, incl f2c-lib)	The functions depend on few variables (some hundred at most). An SLP method with estimation of gradients by linear interpolation of the individual functions on moving simplices, l_infinity exact penalty function as merit function. Inequality constraints only. M. Powell's paper on Direct Search Methods
	DFO	derivative free method of Conn, Scheinberg, and Toint
	NOMADm	Matlab code to do generalized pattern search for nonlinear and mixed variable optimization
	FOCUS	An object-oriented framework for nonlinearly constrained optimization using surrogates, C++.

In the following it is assumed that f, g, h, are differentiable.

f general, bound constraints only

	tn, C-version	use tnbc from this package, truncated Newton method using the Lanczos-process, n should be not too large since identification of binding constraints works inefficiently (classical active set method)
	ve08	for separable convex f , structured quasi Newton method (Toint-Griewank)
	LBFGS-B f90-version, Java version	a limited memory quasi Newton (BFGS) method combined with gradient projection for bound constrained problems; directory contains software, drivers and a user's manual
	TRON	trust region Newton, preconditioned cg, projected search f90-version
	BLMVM	bound-constrained version of the code LMVM. part of the TAO Toolkit
	PL2	truncated Newton method using the Lanczos process with direct computation of a truncated spectral decomposition, uses a so called three directions method from Heinrich, uses directions of negative curvature. for large dimensional problems.
	LM	Several limited memory f77-routines; also for least squares

General linear constraints

	COPL_LC	f convex, interior point method, needs Hessian
	PDCO	f separable convex, primal-dual interior point method (Matlab)

General nonlinear constraints, dense linear algebra

	donlp2	a SQP/SECQP - method, very fast for regular problems, f77, f90, Ansi-C, exact/numerical/automatic gradients, and ps-files on mathematical background AMPL interface, Student binaries of DONLP2 with AMPL for different architectures
	SOLNP	Matlab-SQP solver, IP solver for QP's, includes manual
	NLPLIB	A Matlab Toolbox for Nonlinear Programming and Parameter Estimation
	FFSQP(f77) CFSQP(C)	specifically strong for many inequality constraints; generates iterates which are feasible with respect to inequality constraints, equality constraints split into two inequalities, one dealt with as constraint, the other transferred into a penalty term, ADIFOR interface for automatic differentiation. AMPL interface to CFSQP
	CONMAX	uses ODE's to generate search direction followed by Newton to correct back to feasible region, authors claim it is very robust but somewhat slow.
	CONMIN	old code by Vanderplaats (f77,C++,Manual), f90 version

	General nonlinear constraints, sparse linear algebra
	for high dimensional problems

	LANCELOT-A	transforms a general problem into one with nonlinear equality constraints and bound constraints on (some) variables and solves this using a modification of the Hestenes-Powell multiplier method (book: Conn&Gould&Toint: LANCELOT . Springer Series in Comp. Math. 17) AMPL interface
	LANCELOT-B	part of GALAHAD, updated version, f90
	HQP/OMUSES	motivated by discrete-time optimal control problems, solves general NLP using Powell's or Schittkowski's SQP with Newton-type barrier QP solver, needs Tcl, includes ext. Meschach lib, C++ or SIF input, CUTE interface
	SNOPT	not PD, no_s, solves large-scale linear and nonlinear problems; especially recommended if some of the constraints are highly nonlinear, or constraints respectively their gradients are costly to evaluate and second derivative information is unavailable or hard to obtain; assumes that the number of "free" variables is modest. AMPL interface
	MINOS	also capable of solving nonlinear problems, but not to be recommended for strong nonlinearities, not PD, no_s, AMPL interface
	KNITRO	trust region interior point method, efficient for NLP's of all sizes, AMPL interface
	IPOPT/DYNOPT	interior point method for large NLP, AMPL/CUTE interfaces, automatic discretization of DAE constraints
	MOSEK	solves convex, twice differentiable problems, Win, Linux, Solaris binaries, Matlab and AMPL interface
	LOQO	interior point method, C, no_s, executables for major platforms, work for several months w/o license, AMPL interface, Matlab5 interface
	PENNON	Penalty-barrier code for large general NLPs, AMPL interface
	NLPHOPDM	interior point method, solves convex nonlinear problems, AMPL, GAMS, CUTE/SIF interface

Minimization of Nonsmooth Functions

	NDA	Four different routines for Lipschitz continuous functions subject to linear constraints and for (small) minimax problems
	ACCPM	Analytic center cutting plane method, requires oracle to be written in C. Solaris, Linux, Win32 binaries of library

Semi-infinite Programming

NSIPS

Three different methods (discretization, interior point, SQP dual), uses author's special AMPL interface (C source and Win-binaries)

Mixed Integer Nonlinear Programming

	MINLP World	forum with links to solvers, problem libraries etc
	MINLP_BB	branch&bound and QP/SQP, nominal fee

	BARON	binaries for HP, IBM, Sun, modeling language, websubmission
	BNB	B&B, Matlab, needs optimization toolbox
	FMINCONSET	B&B, variables may be restricted to discrete sets, Matlab, needs optimization toolbox
	mittlp	C, requires CPLEX, extended cutting plane method
	AlphaEcp	WinNt/95 binary, requires CPLEX and f90
	OPBDP binaries	0-1 variables, objective and constraints polynomial (C++) A Davis-Putnam Based Enumeration Algorithm for Linear Pseudo-Boolean Optimization

Network Optimization

Linear objective function

	MCF	C, network simplex method
	Net_simplex

network simplex method, no source ( binaries)
	GIDEN	Graphical Environment for Network Optimization (binaries, requires Java)
	GOBLIN	Tcl/Tk based for graph and network problems (LGPL, C++ source, binaries)
	IPM	interior point method, f77&C
	MCFClass	abstract C++ class for single commodity MCF problems incl 5 solvers: RelaxIV, MCFZIB, CS2, MCFCplex, SPTree
	RelaxIV	MCF solver by Bertsekas&Tseng plus other network and assignment solvers
	Netsoft	Andrew Goldberg's Network Optimization Library in C
	Netsolver	several network codes as Win binaries.
	Martins Netcode	Ernesto Martins' network codes (f77).

Nonlinear objective function

	LSNNO	f77 code from netlib
	PPRN	no_s, library for various platforms
	PFNRN	no_s, nonlinear constraints, Solaris binary

Special/constraint Solvers

	WSAT(OIP)	domain independent local search method for linear integer constraints, no_s, Linux binary has AMPL/CPLEX interface
	CSPLIB/CPlan	C-library for binary constraint satisfaction, application to planning problems
	Filtrane	part of Galahad, nonlinear constraints, filter method, f90
	MVE	Finding the largest ellipsoid inscribing a given polytope, GPL-licensed, Matlab
	Miniball	Finding the smallest enclosing ball of points, GPL-licensed, C++
	Miniball@sourceforge	Finding the smallest enclosing ball of balls, QPL-licensed, C++

Control Problems

	CompEcon Tb	Matlab toolbox for computational economics and finance incl general optimization, dynamic programming, stochastic control
	SLICOT	Control and Systems Library. Very comprehensive.
	IPOPT/DYNOPT	interior point method for large NLP, AMPL/CUTE interfaces, automatic discretization of DAE constraints
	DIRCOL	Direct collocation method. Optimal ODE control problems with control and state constraints are solved as NLPs with NPSOL or SNOPT
	PAREST	A direct multiple shooting method for the numerical solution of optimal control and parameter estimation problems
	Biomimikry	Matlab code for Optimization, Control, and Automation (from upcoming book)
	OCS	SciLab/Maple based to solve unconstrained ODE control problems
	NUDOCCCS and more	Suite of codes to solve general control problems with control and state constraints, sensitivity analysis etc
	SODAS and more	Suite of codes to solve optimal control and related problems especially with DAEs
	OptControlCentre	open source project in dynamic optimization
	HQP/OMUSES	motivated by discrete-time optimal control problems, solves general NLP using Powell's or Schittkowski's SQP with Newton-type barrier QP solver, needs Tcl, includes ext. Meschach lib, C++ or SIF input, CUTE interface
	PDECON	Optimal Control of Ordinary, Algebraic and One-dimensional Partial Differential Equations
	TRICE	Designed to solve discretized PDE-constrained optimization problems with trust region interior point SQP methods

Other collections or problem types

	Modulopt	Fortran 77 codes for smooth and nonsmooth unconstrained, bound-constrained, and general NLP; test problems
	CompEcon Tb	Matlab toolbox for computational economics and finance incl general optimization, dynamic programming, stochastic control
	DAKOTA	A Multilevel Parallel Object-Oriented Framework for Design Optimization, Parameter Estimation, Uncertainty Quantification, and Sensitivity Analysis
	OPT++	An Object-Oriented Nonlinear Optimization Library
	UFO	Interactive System for Optimization, very comprehensive, Win binary only
	WNLib	C-source for various optimization problems
	TOMLAB	Matlab optimization package, comprehensive, with interfaces to many state-of-the-art optimization solvers, e.g. CPLEX , Xpress-MP , MINLP_BB, MIQPBB, filterSQP , PENBMI, PENSDP. It includes SOL software , expensive and non-convex global optimization solvers, approximation methods etc.
	Excel Add-ins	Rich selection for many OR and optimization problems
	PARAM	Klaus Schittkowski's software, especially parameter-identification
	KELLEY	Iterative Methods for Optimization by T. Kelley, codes in Matlab and f77
	SAL	wide selection of basic optimization and OR algorithms, in f77, C, Basic, Pascal, Java, or as DOS/Win binaries
	MATLOG	Facility location and logistics toolbox (Matlab)
	PLT	production/storage/transport, various solvers as Win binaries (in German)
	DistOpt	Solving large-scale problems through decomposition. Requires Ptolemy, works with various free for research or commercial solvers. Tcl/Tk graphics, C++.
	Cheddar	GPL-licensed real-time scheduling simulator, source, Win/Linux/Solaris binaries
	FIR toolbox	Matlab toolbox to optimize FIR filters and similar structures; needs SeDuMi or LOQO or other
	LOLA	a package for planar location problems (solves continuous and discrete cases)
	FUZZY	Fuzzy Optimization (includes StarFLIP++ software)
	MOZART	Advanced development platform based on Oz. Demos include constraint programming, multi-agent, and concurrent applications.
	ECLiPSe	extensive Constraint Logic Programming System, binaries, interfaces to CPLEX and XPRESS-MP
	Constraints	More links to Constraint Systems
	Neural Network Software	Google directory

Back to the top! Date last revised: 10-26-2003