ASCEND - User contributions [en]

Survey of optimisation software

2015-08-13T10:32:35Z

Dimitris: /* Free Open Source Software options */

The following is a survey of optimisation software that was performed as a part of our effort to identify options for a [[Non-proprietary Optimisation]] solver for ASCEND. Feel free to add any that we've missed.

== List of Lists ==

* List of NLP solvers: http://www.ici.ro/camo/hnp.htm
* List of unconstrained optimisation solvers: http://www.ici.ro/camo/huo.htm
* There ''was'' a nice list at http://www.scicomp.uni-erlangen.de/SW/opt.html but the link seems to be broken at the moment.
* 'Decision tree' for optimization software http://plato.asu.edu/sub/nlores.html
* Description of different types of optimisation problems: http://coool.mines.edu/report/node3.html

== Free Open Source Software options ==

* [https://projects.coin-or.org/Ipopt IPOPT] (LGPL) 'Interior-Point Filter Line-Search Algorithm'. Possibly some problems with scaling of variables (according to RPS). can use a number of free and non-free matrix solvers; the free matrix solver in version 3.3.1 is MUMPS. See also [[IPOPT]] in this wiki.
* [http://trilinos.sandia.gov/packages/moocho/ MOOCHO] (GPL?) reduced sequential quadratic programming (SQP); allows the user to supply their own linear solver.
* [http://www.gnu.org/software/gsl/manual/html_node/Multidimensional-Minimization.html GSL 'multimin'] (GPL) several multidimensional dense-matrix unconstrained optimisation methods including conjugate gradient methods, quasi-newton methods, steepest descent and Nelder-Mead simplex method.
* [http://acts.nersc.gov/opt++/index.html OPT++] (free, includes ''optional'' wrapping of non-free NPSOL). Good but dense matrices only (RPS). Superceded by MOOCHO?
* [http://software.sandia.gov/appspack/version5.0/index.html APPSPACK] (GPL?) 'asynchronous parallel generating set search', derivative-free.
* [http://www.eng.buffalo.edu/Research/MODEL/mdo.test.orig/CONMIN/ CONMIN] ('free' but where from?) 'two-step limited memory quasi Newton like Conjugate Gradient method with Beale restarts'.
* [http://www.cs.sandia.gov/SGOPT/ SGOPT] (LGPL) Evolutionary and pattern-search algorithms
* [http://www.math.ufl.edu/~hager/ OPTPACK] (PD) 'a dual algorithm for constrained optimization'
* [http://www.netlib.org/minpack/ MINPACK] (BSD-like) unconstrained
* [http://www.coin-or.org/Bonmin/ BonMin] (CPL) Part of the COIN-OR suite; a solver for convect MINLP problems.
* [https://projects.coin-or.org/Couenne Couenne] (CPL) Part of the COIN-OR suite; a solver for non-convex MINLP problems.
* [http://www.ime.usp.br/~egbirgin/tango/ ALGENCAN] (GPL) Augmented Lagrangian plus an embedded smooth function box-constraint solver called 'GENCAN'
* [http://www.ime.usp.br/~egbirgin/tango/ SPG] (GPL) for smooth function with convex constraint
* [http://www.gerad.ca/~couturgi/NOMAD/ NOMAD] (GPL) Generalized Pattern Search (GPS) algorithms to solve nonlinear optimization problems
* [http://www-fp.mcs.anl.gov/otc/Tools/LBFGS-B/ LBFGS-B] (PD?) limited-memory quasi-Newton code
* [http://ab-initio.mit.edu/wiki/index.php/NLopt NLopt] (LGPL) wrapper for a few other FOSS codes, but also reportedly has some new implementations of certain algorithms
* [http://www.uni-graz.at/imawww/kuntsevich/solvopt/ SolvOpt] (PD) 'method of exact penalisation', based on N.Z. Shor r-algorithm
* [http://openopt.org/ralg ralg] (BSD) - an implementation of N.Z. Shor r-algorithm; nonlinear/nonsmooth constrained/unconstrained problems

'''Metaheuristics'''

* [https://code.google.com/p/popot/ popot] (new BSD license) a C++ Template based library for population based optimization. It includes various population-based optimization algorithms such as particle swarm, ant colonies, evolutionary strategies.
* [http://dev.heuristiclab.com/ HeuristicLab] (GPL) a framework for heuristic and evolutionary algorithms developed by Heuristic and Evolutionary Algorithms Laboratory (HEAL)
* [http://gundog.lbl.gov/GO/index.html GenOpt] (modified BSD license) an optimization program for the minimization of a cost function that is evaluated by an external simulation program, developed by Berkley Lab and written in Java
* [http://jswarm-pso.sourceforge.net/ JSwarm-PSO] (GPL) a Particle Swarm Optimization package written in Java
* [https://pypi.python.org/pypi/ecspy ecpsy] (GNU) a framework for creating evolutionary computations in Python
* [http://psotoolbox.sourceforge.net/ PSO TOOLBOX] (GPL) a Particle Swarm Optimization implementation in Matlab

'''Wrappers'''

* [http://www.coin-or.org/NLPAPI/index.html NLPAPI] (GPL?) a generalised wrapper for NLP solvers, including support for LANCELOT.
* [https://projects.coin-or.org/GAMSlinks/ GAMSlinks] (GPL?) a wrapper for [https://projects.coin-or.org/ COIN-OR] solvers that allows them to be called from GAMS. This is interesting as it shows how we could implement set up ASCEND so that it can use GAMS solvers, which adapting FOSS solvers that run under GAMS much easier to adapt for use with ASCEND.
* [http://www.netlib.org/ampl/solvers/lancelot/ AMPL/LANCELOT] a wrapper for running LANCELOT from AMPL. Again, this provides a way for seeing how solvers that have been adapted for use in AMPL might be also be connected to from ASCEND.
* [http://cuter.rl.ac.uk/cuter-www/interfaces.html CUTEr] (GPL-like license) is a wrapper for a wide range of optimisation solvers, and also a testing framework.
* [https://projects.coin-or.org/Osi OSI] (CPL?) wrapper for quite a wide range of LP solvers, from COIN-OR.
* [https://projects.coin-or.org/OS OS] (CPL?) Optimisation Services, a number of interface languages and APIs for communicating between problem 'servers' and solver 'clients', with support for a range of COIN-OR solvers and converters for GAMS/AMPL input files.
* [http://wiki.services.openoffice.org/wiki/Optimization_Solver OpenOffice.org's Solver]
* [http://openopt.org OpenOpt] (BSD) a general purpose optimization framework written in Python and NumPy, capable of automatic differentiation.
* [http://code.google.com/p/pulp-or/ PuLP] (MIT license) a Python interface for expressing and solving [[LP]] problems.
* [http://rima.incremental.co.nz/ RIMA] (MIT license) a Lua interface for expressing and solving [[LP]] and [[MILP]] problems using CBC, CLP and lpsolve.

'''Unknown:'''

* [http://coool.mines.edu/ COOOL]

Another free list: [http://software.sandia.gov/Acro/html/Main/AcroPackages.html]

There are some more listed in the [ftp://rtfm.mit.edu/pub/usenet/sci.answers/nonlinear-programming-faq nonlinear-programming-faq].

== Free for non-commercial use ==

Trust region

* [http://www.numerical.rl.ac.uk/lancelot/blurb.html LANCELOT] (no redistribution or resale) Trust region method, adapt for bound constraints

Active set

* [http://www-unix.mcs.anl.gov/~more/tron/ TRON] (permission to copy and modify, but only to be used for 'internal research' ([http://plato.asu.edu/ftp/other_software/tron_f90.tar.gz download]) active set method that uses a combination of gradient projections and a preconditioned conjugate gradient method to minimize an objective function. TRON only provides for 'box' constraints and has no support for equality constraints, although it may be possible to add support for that by wrapping TRON around an NLA solver?

Sequential quadratic programming

* [http://plato.la.asu.edu/donlp2.html DONLP2] (dense; free for non-commercial purposes)

== Some proprietary alternatives ==

Generalised reduced gradient method:

* [[CONOPT]] (plus others in certain cases)
* [http://www.sbsi-sol-optimize.com/asp/sol_product_minos.htm MINOS] (uses GRG for linear constraints, else 'sparse SLC algorithm (a projected Lagrangian method, related to Robinson's method)' for nonlinear constraints. Used when gradient evaluation is cheap.
* MS Excel [http://support.microsoft.com/kb/q214115/ Solver].
* GRG2
* LSGRG2
* [http://www.pinterconsulting.com/ LGO] 'Lipschitz Global Optimizer'

Sequential quadratic programming:

* [http://www.sbsi-sol-optimize.com/asp/sol_products_snopt_desc.htm SNOPT] (sparse) Used when gradient evaluation is expensive. 'SNOPT employs a sparse SQP algorithm with limited-memory quasi-Newton approximations to the Hessian of Lagrangian. An augmented Lagrangian merit function promotes convergence from an arbitrary point.'
* [http://www.uni-bayreuth.de/departments/math/~kschittkowski/nlpqlp22.htm NLPQLP]
* [http://www.sbsi-sol-optimize.com/asp/sol_product_npsol.htm NPSOL]
* [http://www.sbsi-sol-optimize.com/asp/sol_lssol105description.htm LSSOL] (dense, 'two-phase (primal) quadratic programming')
* [http://www.princeton.edu/~rvdb/ LOQO] (free 30-day trial) 'LOQO is based on an infeasible, primal-dual, interior-point method applied to a sequence of quadratic approximations to the given problem'
* [http://www.mcs.anl.gov/~leyffer/solvers.html FilterSQP]

Active set method:

* [http://www.sbsi-sol-optimize.com/asp/sol_product_qpopt.htm QPOPT] (dense)

Other methods:

* [http://www.ziena.com/knitro.htm KNITRO] (three methods: interior point direct, interior point conjugate gradient, 'active set')
* [http://www.gams.com/dd/docs/solvers/pathnlp.pdf PATHNLP]. 'PATHNLP solves an NLP by internally constructing the Karush-Kuhn-Tucker (KKT) system of first-order optimality conditions associated with the NLP and solving this system using the PATH solver for complementarity problems'. Supposedly good for convex problems.
* [http://www.mosek.com/products.html MOSEK] (limited version available for download, or free student license) Interior point method plus simplex method.
* [http://www2.am.uni-erlangen.de/~kocvara/pennon/ PENNON] 'penalty method', 'PBM method of Ben-Tal and Zibulevsky'

Global optimisation

* [http://www.andrew.cmu.edu/user/ns1b/baron/baron.html BARON]
* [http://www.ganso.com.au/index.php GANSO]

Methods not yet checked:

* IMSL and NAG software libraries
''More to come''

Mixed integer/nonlinear programs:

* [http://www.gams.com/solvers/solvers.htm#DICOPT DICOPT]: MINLP

See also [[Survey of sparse matrix software]]

[[Category:Development]]
[[Category:Miscellany]]

Survey of optimisation software

2015-08-13T10:31:58Z

Dimitris: /* Free Open Source Software options */

The following is a survey of optimisation software that was performed as a part of our effort to identify options for a [[Non-proprietary Optimisation]] solver for ASCEND. Feel free to add any that we've missed.

== List of Lists ==

* List of NLP solvers: http://www.ici.ro/camo/hnp.htm
* List of unconstrained optimisation solvers: http://www.ici.ro/camo/huo.htm
* There ''was'' a nice list at http://www.scicomp.uni-erlangen.de/SW/opt.html but the link seems to be broken at the moment.
* 'Decision tree' for optimization software http://plato.asu.edu/sub/nlores.html
* Description of different types of optimisation problems: http://coool.mines.edu/report/node3.html

== Free Open Source Software options ==

* [https://projects.coin-or.org/Ipopt IPOPT] (LGPL) 'Interior-Point Filter Line-Search Algorithm'. Possibly some problems with scaling of variables (according to RPS). can use a number of free and non-free matrix solvers; the free matrix solver in version 3.3.1 is MUMPS. See also [[IPOPT]] in this wiki.
* [http://trilinos.sandia.gov/packages/moocho/ MOOCHO] (GPL?) reduced sequential quadratic programming (SQP); allows the user to supply their own linear solver.
* [http://www.gnu.org/software/gsl/manual/html_node/Multidimensional-Minimization.html GSL 'multimin'] (GPL) several multidimensional dense-matrix unconstrained optimisation methods including conjugate gradient methods, quasi-newton methods, steepest descent and Nelder-Mead simplex method.
* [http://acts.nersc.gov/opt++/index.html OPT++] (free, includes ''optional'' wrapping of non-free NPSOL). Good but dense matrices only (RPS). Superceded by MOOCHO?
* [http://software.sandia.gov/appspack/version5.0/index.html APPSPACK] (GPL?) 'asynchronous parallel generating set search', derivative-free.
* [http://www.eng.buffalo.edu/Research/MODEL/mdo.test.orig/CONMIN/ CONMIN] ('free' but where from?) 'two-step limited memory quasi Newton like Conjugate Gradient method with Beale restarts'.
* [http://www.cs.sandia.gov/SGOPT/ SGOPT] (LGPL) Evolutionary and pattern-search algorithms
* [http://www.math.ufl.edu/~hager/ OPTPACK] (PD) 'a dual algorithm for constrained optimization'
* [http://www.netlib.org/minpack/ MINPACK] (BSD-like) unconstrained
* [http://www.coin-or.org/Bonmin/ BonMin] (CPL) Part of the COIN-OR suite; a solver for convect MINLP problems.
* [https://projects.coin-or.org/Couenne Couenne] (CPL) Part of the COIN-OR suite; a solver for non-convex MINLP problems.
* [http://www.ime.usp.br/~egbirgin/tango/ ALGENCAN] (GPL) Augmented Lagrangian plus an embedded smooth function box-constraint solver called 'GENCAN'
* [http://www.ime.usp.br/~egbirgin/tango/ SPG] (GPL) for smooth function with convex constraint
* [http://www.gerad.ca/~couturgi/NOMAD/ NOMAD] (GPL) Generalized Pattern Search (GPS) algorithms to solve nonlinear optimization problems
* [http://www-fp.mcs.anl.gov/otc/Tools/LBFGS-B/ LBFGS-B] (PD?) limited-memory quasi-Newton code
* [http://ab-initio.mit.edu/wiki/index.php/NLopt NLopt] (LGPL) wrapper for a few other FOSS codes, but also reportedly has some new implementations of certain algorithms
* [http://www.uni-graz.at/imawww/kuntsevich/solvopt/ SolvOpt] (PD) 'method of exact penalisation', based on N.Z. Shor r-algorithm
* [http://openopt.org/ralg ralg] (BSD) - an implementation of N.Z. Shor r-algorithm; nonlinear/nonsmooth constrained/unconstrained problems

'''Metaheuristics'''

* [https://code.google.com/p/popot/ popot] (new BSD license) a C++ Template based library for population based optimization. It includes various population-based optimization algorithms such as particle swarm, ant colonies, evolutionary strategies.
* [http://dev.heuristiclab.com/ HeuristicLab] (GPL) a framework for heuristic and evolutionary algorithms developed by Heuristic and Evolutionary Algorithms Laboratory (HEAL)
* [http://gundog.lbl.gov/GO/index.html GenOpt] (modified BSD license) an optimization program for the minimization of a cost function that is evaluated by an external simulation program, developed by Berkley Lab and written in Java
* [http://jswarm-pso.sourceforge.net/ JSwarm-PSO] (GPL) a Particle Swarm Optimization package written in Java
* [https://pypi.python.org/pypi/ecspy ecpsy] (GNU) a framework for creating evolutionary computations in Python
* [http://psotoolbox.sourceforge.net/ PSO TOOLBOX] (GNU) a Particle Swarm Optimization implementation in Matlab

'''Wrappers'''

* [http://www.coin-or.org/NLPAPI/index.html NLPAPI] (GPL?) a generalised wrapper for NLP solvers, including support for LANCELOT.
* [https://projects.coin-or.org/GAMSlinks/ GAMSlinks] (GPL?) a wrapper for [https://projects.coin-or.org/ COIN-OR] solvers that allows them to be called from GAMS. This is interesting as it shows how we could implement set up ASCEND so that it can use GAMS solvers, which adapting FOSS solvers that run under GAMS much easier to adapt for use with ASCEND.
* [http://www.netlib.org/ampl/solvers/lancelot/ AMPL/LANCELOT] a wrapper for running LANCELOT from AMPL. Again, this provides a way for seeing how solvers that have been adapted for use in AMPL might be also be connected to from ASCEND.
* [http://cuter.rl.ac.uk/cuter-www/interfaces.html CUTEr] (GPL-like license) is a wrapper for a wide range of optimisation solvers, and also a testing framework.
* [https://projects.coin-or.org/Osi OSI] (CPL?) wrapper for quite a wide range of LP solvers, from COIN-OR.
* [https://projects.coin-or.org/OS OS] (CPL?) Optimisation Services, a number of interface languages and APIs for communicating between problem 'servers' and solver 'clients', with support for a range of COIN-OR solvers and converters for GAMS/AMPL input files.
* [http://wiki.services.openoffice.org/wiki/Optimization_Solver OpenOffice.org's Solver]
* [http://openopt.org OpenOpt] (BSD) a general purpose optimization framework written in Python and NumPy, capable of automatic differentiation.
* [http://code.google.com/p/pulp-or/ PuLP] (MIT license) a Python interface for expressing and solving [[LP]] problems.
* [http://rima.incremental.co.nz/ RIMA] (MIT license) a Lua interface for expressing and solving [[LP]] and [[MILP]] problems using CBC, CLP and lpsolve.

'''Unknown:'''

* [http://coool.mines.edu/ COOOL]

Another free list: [http://software.sandia.gov/Acro/html/Main/AcroPackages.html]

There are some more listed in the [ftp://rtfm.mit.edu/pub/usenet/sci.answers/nonlinear-programming-faq nonlinear-programming-faq].

== Free for non-commercial use ==

Trust region

* [http://www.numerical.rl.ac.uk/lancelot/blurb.html LANCELOT] (no redistribution or resale) Trust region method, adapt for bound constraints

Active set

* [http://www-unix.mcs.anl.gov/~more/tron/ TRON] (permission to copy and modify, but only to be used for 'internal research' ([http://plato.asu.edu/ftp/other_software/tron_f90.tar.gz download]) active set method that uses a combination of gradient projections and a preconditioned conjugate gradient method to minimize an objective function. TRON only provides for 'box' constraints and has no support for equality constraints, although it may be possible to add support for that by wrapping TRON around an NLA solver?

Sequential quadratic programming

* [http://plato.la.asu.edu/donlp2.html DONLP2] (dense; free for non-commercial purposes)

== Some proprietary alternatives ==

Generalised reduced gradient method:

* [[CONOPT]] (plus others in certain cases)
* [http://www.sbsi-sol-optimize.com/asp/sol_product_minos.htm MINOS] (uses GRG for linear constraints, else 'sparse SLC algorithm (a projected Lagrangian method, related to Robinson's method)' for nonlinear constraints. Used when gradient evaluation is cheap.
* MS Excel [http://support.microsoft.com/kb/q214115/ Solver].
* GRG2
* LSGRG2
* [http://www.pinterconsulting.com/ LGO] 'Lipschitz Global Optimizer'

Sequential quadratic programming:

* [http://www.sbsi-sol-optimize.com/asp/sol_products_snopt_desc.htm SNOPT] (sparse) Used when gradient evaluation is expensive. 'SNOPT employs a sparse SQP algorithm with limited-memory quasi-Newton approximations to the Hessian of Lagrangian. An augmented Lagrangian merit function promotes convergence from an arbitrary point.'
* [http://www.uni-bayreuth.de/departments/math/~kschittkowski/nlpqlp22.htm NLPQLP]
* [http://www.sbsi-sol-optimize.com/asp/sol_product_npsol.htm NPSOL]
* [http://www.sbsi-sol-optimize.com/asp/sol_lssol105description.htm LSSOL] (dense, 'two-phase (primal) quadratic programming')
* [http://www.princeton.edu/~rvdb/ LOQO] (free 30-day trial) 'LOQO is based on an infeasible, primal-dual, interior-point method applied to a sequence of quadratic approximations to the given problem'
* [http://www.mcs.anl.gov/~leyffer/solvers.html FilterSQP]

Active set method:

* [http://www.sbsi-sol-optimize.com/asp/sol_product_qpopt.htm QPOPT] (dense)

Other methods:

* [http://www.ziena.com/knitro.htm KNITRO] (three methods: interior point direct, interior point conjugate gradient, 'active set')
* [http://www.gams.com/dd/docs/solvers/pathnlp.pdf PATHNLP]. 'PATHNLP solves an NLP by internally constructing the Karush-Kuhn-Tucker (KKT) system of first-order optimality conditions associated with the NLP and solving this system using the PATH solver for complementarity problems'. Supposedly good for convex problems.
* [http://www.mosek.com/products.html MOSEK] (limited version available for download, or free student license) Interior point method plus simplex method.
* [http://www2.am.uni-erlangen.de/~kocvara/pennon/ PENNON] 'penalty method', 'PBM method of Ben-Tal and Zibulevsky'

Global optimisation

* [http://www.andrew.cmu.edu/user/ns1b/baron/baron.html BARON]
* [http://www.ganso.com.au/index.php GANSO]

Methods not yet checked:

* IMSL and NAG software libraries
''More to come''

Mixed integer/nonlinear programs:

* [http://www.gams.com/solvers/solvers.htm#DICOPT DICOPT]: MINLP

See also [[Survey of sparse matrix software]]

[[Category:Development]]
[[Category:Miscellany]]

Survey of optimisation software

2015-08-13T10:31:30Z

Dimitris: /* Free Open Source Software options */

The following is a survey of optimisation software that was performed as a part of our effort to identify options for a [[Non-proprietary Optimisation]] solver for ASCEND. Feel free to add any that we've missed.

== List of Lists ==

* List of NLP solvers: http://www.ici.ro/camo/hnp.htm
* List of unconstrained optimisation solvers: http://www.ici.ro/camo/huo.htm
* There ''was'' a nice list at http://www.scicomp.uni-erlangen.de/SW/opt.html but the link seems to be broken at the moment.
* 'Decision tree' for optimization software http://plato.asu.edu/sub/nlores.html
* Description of different types of optimisation problems: http://coool.mines.edu/report/node3.html

== Free Open Source Software options ==

* [https://projects.coin-or.org/Ipopt IPOPT] (LGPL) 'Interior-Point Filter Line-Search Algorithm'. Possibly some problems with scaling of variables (according to RPS). can use a number of free and non-free matrix solvers; the free matrix solver in version 3.3.1 is MUMPS. See also [[IPOPT]] in this wiki.
* [http://trilinos.sandia.gov/packages/moocho/ MOOCHO] (GPL?) reduced sequential quadratic programming (SQP); allows the user to supply their own linear solver.
* [http://www.gnu.org/software/gsl/manual/html_node/Multidimensional-Minimization.html GSL 'multimin'] (GPL) several multidimensional dense-matrix unconstrained optimisation methods including conjugate gradient methods, quasi-newton methods, steepest descent and Nelder-Mead simplex method.
* [http://acts.nersc.gov/opt++/index.html OPT++] (free, includes ''optional'' wrapping of non-free NPSOL). Good but dense matrices only (RPS). Superceded by MOOCHO?
* [http://software.sandia.gov/appspack/version5.0/index.html APPSPACK] (GPL?) 'asynchronous parallel generating set search', derivative-free.
* [http://www.eng.buffalo.edu/Research/MODEL/mdo.test.orig/CONMIN/ CONMIN] ('free' but where from?) 'two-step limited memory quasi Newton like Conjugate Gradient method with Beale restarts'.
* [http://www.cs.sandia.gov/SGOPT/ SGOPT] (LGPL) Evolutionary and pattern-search algorithms
* [http://www.math.ufl.edu/~hager/ OPTPACK] (PD) 'a dual algorithm for constrained optimization'
* [http://www.netlib.org/minpack/ MINPACK] (BSD-like) unconstrained
* [http://www.coin-or.org/Bonmin/ BonMin] (CPL) Part of the COIN-OR suite; a solver for convect MINLP problems.
* [https://projects.coin-or.org/Couenne Couenne] (CPL) Part of the COIN-OR suite; a solver for non-convex MINLP problems.
* [http://www.ime.usp.br/~egbirgin/tango/ ALGENCAN] (GPL) Augmented Lagrangian plus an embedded smooth function box-constraint solver called 'GENCAN'
* [http://www.ime.usp.br/~egbirgin/tango/ SPG] (GPL) for smooth function with convex constraint
* [http://www.gerad.ca/~couturgi/NOMAD/ NOMAD] (GPL) Generalized Pattern Search (GPS) algorithms to solve nonlinear optimization problems
* [http://www-fp.mcs.anl.gov/otc/Tools/LBFGS-B/ LBFGS-B] (PD?) limited-memory quasi-Newton code
* [http://ab-initio.mit.edu/wiki/index.php/NLopt NLopt] (LGPL) wrapper for a few other FOSS codes, but also reportedly has some new implementations of certain algorithms
* [http://www.uni-graz.at/imawww/kuntsevich/solvopt/ SolvOpt] (PD) 'method of exact penalisation', based on N.Z. Shor r-algorithm
* [http://openopt.org/ralg ralg] (BSD) - an implementation of N.Z. Shor r-algorithm; nonlinear/nonsmooth constrained/unconstrained problems

'''Metaheuristics'''

* [https://code.google.com/p/popot/ popot] (new BSD license) a C++ Template based library for population based optimization. It includes various population-based optimization algorithms such as particle swarm, ant colonies, evolutionary strategies.
* [http://dev.heuristiclab.com/ HeuristicLab] (GPL) a framework for heuristic and evolutionary algorithms developed by Heuristic and Evolutionary Algorithms Laboratory (HEAL)
* [http://gundog.lbl.gov/GO/index.html GenOpt] (modified BSD license) an optimization program for the minimization of a cost function that is evaluated by an external simulation program, developed by Berkley Lab and written in Java
* [http://jswarm-pso.sourceforge.net/ JSwarm-PSO] (GPL) a Particle swarm optimization package written in Java
* [https://pypi.python.org/pypi/ecspy ecpsy] (GNU) a framework for creating evolutionary computations in Python
* [http://psotoolbox.sourceforge.net/ PSO TOOLBOX] (GNU) a Particle Swarm Optimization implementation in Matlab

'''Wrappers'''

* [http://www.coin-or.org/NLPAPI/index.html NLPAPI] (GPL?) a generalised wrapper for NLP solvers, including support for LANCELOT.
* [https://projects.coin-or.org/GAMSlinks/ GAMSlinks] (GPL?) a wrapper for [https://projects.coin-or.org/ COIN-OR] solvers that allows them to be called from GAMS. This is interesting as it shows how we could implement set up ASCEND so that it can use GAMS solvers, which adapting FOSS solvers that run under GAMS much easier to adapt for use with ASCEND.
* [http://www.netlib.org/ampl/solvers/lancelot/ AMPL/LANCELOT] a wrapper for running LANCELOT from AMPL. Again, this provides a way for seeing how solvers that have been adapted for use in AMPL might be also be connected to from ASCEND.
* [http://cuter.rl.ac.uk/cuter-www/interfaces.html CUTEr] (GPL-like license) is a wrapper for a wide range of optimisation solvers, and also a testing framework.
* [https://projects.coin-or.org/Osi OSI] (CPL?) wrapper for quite a wide range of LP solvers, from COIN-OR.
* [https://projects.coin-or.org/OS OS] (CPL?) Optimisation Services, a number of interface languages and APIs for communicating between problem 'servers' and solver 'clients', with support for a range of COIN-OR solvers and converters for GAMS/AMPL input files.
* [http://wiki.services.openoffice.org/wiki/Optimization_Solver OpenOffice.org's Solver]
* [http://openopt.org OpenOpt] (BSD) a general purpose optimization framework written in Python and NumPy, capable of automatic differentiation.
* [http://code.google.com/p/pulp-or/ PuLP] (MIT license) a Python interface for expressing and solving [[LP]] problems.
* [http://rima.incremental.co.nz/ RIMA] (MIT license) a Lua interface for expressing and solving [[LP]] and [[MILP]] problems using CBC, CLP and lpsolve.

'''Unknown:'''

* [http://coool.mines.edu/ COOOL]

Another free list: [http://software.sandia.gov/Acro/html/Main/AcroPackages.html]

There are some more listed in the [ftp://rtfm.mit.edu/pub/usenet/sci.answers/nonlinear-programming-faq nonlinear-programming-faq].

== Free for non-commercial use ==

Trust region

* [http://www.numerical.rl.ac.uk/lancelot/blurb.html LANCELOT] (no redistribution or resale) Trust region method, adapt for bound constraints

Active set

* [http://www-unix.mcs.anl.gov/~more/tron/ TRON] (permission to copy and modify, but only to be used for 'internal research' ([http://plato.asu.edu/ftp/other_software/tron_f90.tar.gz download]) active set method that uses a combination of gradient projections and a preconditioned conjugate gradient method to minimize an objective function. TRON only provides for 'box' constraints and has no support for equality constraints, although it may be possible to add support for that by wrapping TRON around an NLA solver?

Sequential quadratic programming

* [http://plato.la.asu.edu/donlp2.html DONLP2] (dense; free for non-commercial purposes)

== Some proprietary alternatives ==

Generalised reduced gradient method:

* [[CONOPT]] (plus others in certain cases)
* [http://www.sbsi-sol-optimize.com/asp/sol_product_minos.htm MINOS] (uses GRG for linear constraints, else 'sparse SLC algorithm (a projected Lagrangian method, related to Robinson's method)' for nonlinear constraints. Used when gradient evaluation is cheap.
* MS Excel [http://support.microsoft.com/kb/q214115/ Solver].
* GRG2
* LSGRG2
* [http://www.pinterconsulting.com/ LGO] 'Lipschitz Global Optimizer'

Sequential quadratic programming:

* [http://www.sbsi-sol-optimize.com/asp/sol_products_snopt_desc.htm SNOPT] (sparse) Used when gradient evaluation is expensive. 'SNOPT employs a sparse SQP algorithm with limited-memory quasi-Newton approximations to the Hessian of Lagrangian. An augmented Lagrangian merit function promotes convergence from an arbitrary point.'
* [http://www.uni-bayreuth.de/departments/math/~kschittkowski/nlpqlp22.htm NLPQLP]
* [http://www.sbsi-sol-optimize.com/asp/sol_product_npsol.htm NPSOL]
* [http://www.sbsi-sol-optimize.com/asp/sol_lssol105description.htm LSSOL] (dense, 'two-phase (primal) quadratic programming')
* [http://www.princeton.edu/~rvdb/ LOQO] (free 30-day trial) 'LOQO is based on an infeasible, primal-dual, interior-point method applied to a sequence of quadratic approximations to the given problem'
* [http://www.mcs.anl.gov/~leyffer/solvers.html FilterSQP]

Active set method:

* [http://www.sbsi-sol-optimize.com/asp/sol_product_qpopt.htm QPOPT] (dense)

Other methods:

* [http://www.ziena.com/knitro.htm KNITRO] (three methods: interior point direct, interior point conjugate gradient, 'active set')
* [http://www.gams.com/dd/docs/solvers/pathnlp.pdf PATHNLP]. 'PATHNLP solves an NLP by internally constructing the Karush-Kuhn-Tucker (KKT) system of first-order optimality conditions associated with the NLP and solving this system using the PATH solver for complementarity problems'. Supposedly good for convex problems.
* [http://www.mosek.com/products.html MOSEK] (limited version available for download, or free student license) Interior point method plus simplex method.
* [http://www2.am.uni-erlangen.de/~kocvara/pennon/ PENNON] 'penalty method', 'PBM method of Ben-Tal and Zibulevsky'

Global optimisation

* [http://www.andrew.cmu.edu/user/ns1b/baron/baron.html BARON]
* [http://www.ganso.com.au/index.php GANSO]

Methods not yet checked:

* IMSL and NAG software libraries
''More to come''

Mixed integer/nonlinear programs:

* [http://www.gams.com/solvers/solvers.htm#DICOPT DICOPT]: MINLP

See also [[Survey of sparse matrix software]]

[[Category:Development]]
[[Category:Miscellany]]

Survey of optimisation software

2015-08-13T10:28:45Z

Dimitris: /* Free Open Source Software options */

The following is a survey of optimisation software that was performed as a part of our effort to identify options for a [[Non-proprietary Optimisation]] solver for ASCEND. Feel free to add any that we've missed.

== List of Lists ==

* List of NLP solvers: http://www.ici.ro/camo/hnp.htm
* List of unconstrained optimisation solvers: http://www.ici.ro/camo/huo.htm
* There ''was'' a nice list at http://www.scicomp.uni-erlangen.de/SW/opt.html but the link seems to be broken at the moment.
* 'Decision tree' for optimization software http://plato.asu.edu/sub/nlores.html
* Description of different types of optimisation problems: http://coool.mines.edu/report/node3.html

== Free Open Source Software options ==

* [https://projects.coin-or.org/Ipopt IPOPT] (LGPL) 'Interior-Point Filter Line-Search Algorithm'. Possibly some problems with scaling of variables (according to RPS). can use a number of free and non-free matrix solvers; the free matrix solver in version 3.3.1 is MUMPS. See also [[IPOPT]] in this wiki.
* [http://trilinos.sandia.gov/packages/moocho/ MOOCHO] (GPL?) reduced sequential quadratic programming (SQP); allows the user to supply their own linear solver.
* [http://www.gnu.org/software/gsl/manual/html_node/Multidimensional-Minimization.html GSL 'multimin'] (GPL) several multidimensional dense-matrix unconstrained optimisation methods including conjugate gradient methods, quasi-newton methods, steepest descent and Nelder-Mead simplex method.
* [http://acts.nersc.gov/opt++/index.html OPT++] (free, includes ''optional'' wrapping of non-free NPSOL). Good but dense matrices only (RPS). Superceded by MOOCHO?
* [http://software.sandia.gov/appspack/version5.0/index.html APPSPACK] (GPL?) 'asynchronous parallel generating set search', derivative-free.
* [http://www.eng.buffalo.edu/Research/MODEL/mdo.test.orig/CONMIN/ CONMIN] ('free' but where from?) 'two-step limited memory quasi Newton like Conjugate Gradient method with Beale restarts'.
* [http://www.cs.sandia.gov/SGOPT/ SGOPT] (LGPL) Evolutionary and pattern-search algorithms
* [http://www.math.ufl.edu/~hager/ OPTPACK] (PD) 'a dual algorithm for constrained optimization'
* [http://www.netlib.org/minpack/ MINPACK] (BSD-like) unconstrained
* [http://www.coin-or.org/Bonmin/ BonMin] (CPL) Part of the COIN-OR suite; a solver for convect MINLP problems.
* [https://projects.coin-or.org/Couenne Couenne] (CPL) Part of the COIN-OR suite; a solver for non-convex MINLP problems.
* [http://www.ime.usp.br/~egbirgin/tango/ ALGENCAN] (GPL) Augmented Lagrangian plus an embedded smooth function box-constraint solver called 'GENCAN'
* [http://www.ime.usp.br/~egbirgin/tango/ SPG] (GPL) for smooth function with convex constraint
* [http://www.gerad.ca/~couturgi/NOMAD/ NOMAD] (GPL) Generalized Pattern Search (GPS) algorithms to solve nonlinear optimization problems
* [http://www-fp.mcs.anl.gov/otc/Tools/LBFGS-B/ LBFGS-B] (PD?) limited-memory quasi-Newton code
* [http://ab-initio.mit.edu/wiki/index.php/NLopt NLopt] (LGPL) wrapper for a few other FOSS codes, but also reportedly has some new implementations of certain algorithms
* [http://www.uni-graz.at/imawww/kuntsevich/solvopt/ SolvOpt] (PD) 'method of exact penalisation', based on N.Z. Shor r-algorithm
* [http://openopt.org/ralg ralg] (BSD) - an implementation of N.Z. Shor r-algorithm; nonlinear/nonsmooth constrained/unconstrained problems

'''Metaheuristics'''

* [https://code.google.com/p/popot/ popot] (new BSD license) a C++ Template based library for population based optimization. It includes various population-based optimization algorithms such as particle swarm, ant colonies, evolutionary strategies.
* [http://dev.heuristiclab.com/ HeuristicLab] (GPL) a framework for heuristic and evolutionary algorithms developed by Heuristic and Evolutionary Algorithms Laboratory (HEAL)
* [http://gundog.lbl.gov/GO/index.html GenOpt] (modified BSD license) an optimization program for the minimization of a cost function that is evaluated by an external simulation program, developed by Berkley Lab and written in Java
* [http://jswarm-pso.sourceforge.net/ JSwarm-PSO] (GPL) a Particle swarm optimization package written in Java
* [https://pypi.python.org/pypi/ecspy ecpsy] (GNU) a framework for creating evolutionary computations in Python

'''Wrappers'''

* [http://www.coin-or.org/NLPAPI/index.html NLPAPI] (GPL?) a generalised wrapper for NLP solvers, including support for LANCELOT.
* [https://projects.coin-or.org/GAMSlinks/ GAMSlinks] (GPL?) a wrapper for [https://projects.coin-or.org/ COIN-OR] solvers that allows them to be called from GAMS. This is interesting as it shows how we could implement set up ASCEND so that it can use GAMS solvers, which adapting FOSS solvers that run under GAMS much easier to adapt for use with ASCEND.
* [http://www.netlib.org/ampl/solvers/lancelot/ AMPL/LANCELOT] a wrapper for running LANCELOT from AMPL. Again, this provides a way for seeing how solvers that have been adapted for use in AMPL might be also be connected to from ASCEND.
* [http://cuter.rl.ac.uk/cuter-www/interfaces.html CUTEr] (GPL-like license) is a wrapper for a wide range of optimisation solvers, and also a testing framework.
* [https://projects.coin-or.org/Osi OSI] (CPL?) wrapper for quite a wide range of LP solvers, from COIN-OR.
* [https://projects.coin-or.org/OS OS] (CPL?) Optimisation Services, a number of interface languages and APIs for communicating between problem 'servers' and solver 'clients', with support for a range of COIN-OR solvers and converters for GAMS/AMPL input files.
* [http://wiki.services.openoffice.org/wiki/Optimization_Solver OpenOffice.org's Solver]
* [http://openopt.org OpenOpt] (BSD) a general purpose optimization framework written in Python and NumPy, capable of automatic differentiation.
* [http://code.google.com/p/pulp-or/ PuLP] (MIT license) a Python interface for expressing and solving [[LP]] problems.
* [http://rima.incremental.co.nz/ RIMA] (MIT license) a Lua interface for expressing and solving [[LP]] and [[MILP]] problems using CBC, CLP and lpsolve.

'''Unknown:'''

* [http://coool.mines.edu/ COOOL]

Another free list: [http://software.sandia.gov/Acro/html/Main/AcroPackages.html]

There are some more listed in the [ftp://rtfm.mit.edu/pub/usenet/sci.answers/nonlinear-programming-faq nonlinear-programming-faq].

== Free for non-commercial use ==

Trust region

* [http://www.numerical.rl.ac.uk/lancelot/blurb.html LANCELOT] (no redistribution or resale) Trust region method, adapt for bound constraints

Active set

* [http://www-unix.mcs.anl.gov/~more/tron/ TRON] (permission to copy and modify, but only to be used for 'internal research' ([http://plato.asu.edu/ftp/other_software/tron_f90.tar.gz download]) active set method that uses a combination of gradient projections and a preconditioned conjugate gradient method to minimize an objective function. TRON only provides for 'box' constraints and has no support for equality constraints, although it may be possible to add support for that by wrapping TRON around an NLA solver?

Sequential quadratic programming

* [http://plato.la.asu.edu/donlp2.html DONLP2] (dense; free for non-commercial purposes)

== Some proprietary alternatives ==

Generalised reduced gradient method:

* [[CONOPT]] (plus others in certain cases)
* [http://www.sbsi-sol-optimize.com/asp/sol_product_minos.htm MINOS] (uses GRG for linear constraints, else 'sparse SLC algorithm (a projected Lagrangian method, related to Robinson's method)' for nonlinear constraints. Used when gradient evaluation is cheap.
* MS Excel [http://support.microsoft.com/kb/q214115/ Solver].
* GRG2
* LSGRG2
* [http://www.pinterconsulting.com/ LGO] 'Lipschitz Global Optimizer'

Sequential quadratic programming:

* [http://www.sbsi-sol-optimize.com/asp/sol_products_snopt_desc.htm SNOPT] (sparse) Used when gradient evaluation is expensive. 'SNOPT employs a sparse SQP algorithm with limited-memory quasi-Newton approximations to the Hessian of Lagrangian. An augmented Lagrangian merit function promotes convergence from an arbitrary point.'
* [http://www.uni-bayreuth.de/departments/math/~kschittkowski/nlpqlp22.htm NLPQLP]
* [http://www.sbsi-sol-optimize.com/asp/sol_product_npsol.htm NPSOL]
* [http://www.sbsi-sol-optimize.com/asp/sol_lssol105description.htm LSSOL] (dense, 'two-phase (primal) quadratic programming')
* [http://www.princeton.edu/~rvdb/ LOQO] (free 30-day trial) 'LOQO is based on an infeasible, primal-dual, interior-point method applied to a sequence of quadratic approximations to the given problem'
* [http://www.mcs.anl.gov/~leyffer/solvers.html FilterSQP]

Active set method:

* [http://www.sbsi-sol-optimize.com/asp/sol_product_qpopt.htm QPOPT] (dense)

Other methods:

* [http://www.ziena.com/knitro.htm KNITRO] (three methods: interior point direct, interior point conjugate gradient, 'active set')
* [http://www.gams.com/dd/docs/solvers/pathnlp.pdf PATHNLP]. 'PATHNLP solves an NLP by internally constructing the Karush-Kuhn-Tucker (KKT) system of first-order optimality conditions associated with the NLP and solving this system using the PATH solver for complementarity problems'. Supposedly good for convex problems.
* [http://www.mosek.com/products.html MOSEK] (limited version available for download, or free student license) Interior point method plus simplex method.
* [http://www2.am.uni-erlangen.de/~kocvara/pennon/ PENNON] 'penalty method', 'PBM method of Ben-Tal and Zibulevsky'

Global optimisation

* [http://www.andrew.cmu.edu/user/ns1b/baron/baron.html BARON]
* [http://www.ganso.com.au/index.php GANSO]

Methods not yet checked:

* IMSL and NAG software libraries
''More to come''

Mixed integer/nonlinear programs:

* [http://www.gams.com/solvers/solvers.htm#DICOPT DICOPT]: MINLP

See also [[Survey of sparse matrix software]]

[[Category:Development]]
[[Category:Miscellany]]

Survey of optimisation software

2015-08-11T09:43:41Z

Dimitris: /* Free Open Source Software options */

The following is a survey of optimisation software that was performed as a part of our effort to identify options for a [[Non-proprietary Optimisation]] solver for ASCEND. Feel free to add any that we've missed.

== List of Lists ==

* List of NLP solvers: http://www.ici.ro/camo/hnp.htm
* List of unconstrained optimisation solvers: http://www.ici.ro/camo/huo.htm
* There ''was'' a nice list at http://www.scicomp.uni-erlangen.de/SW/opt.html but the link seems to be broken at the moment.
* 'Decision tree' for optimization software http://plato.asu.edu/sub/nlores.html
* Description of different types of optimisation problems: http://coool.mines.edu/report/node3.html

== Free Open Source Software options ==

* [https://projects.coin-or.org/Ipopt IPOPT] (LGPL) 'Interior-Point Filter Line-Search Algorithm'. Possibly some problems with scaling of variables (according to RPS). can use a number of free and non-free matrix solvers; the free matrix solver in version 3.3.1 is MUMPS. See also [[IPOPT]] in this wiki.
* [http://trilinos.sandia.gov/packages/moocho/ MOOCHO] (GPL?) reduced sequential quadratic programming (SQP); allows the user to supply their own linear solver.
* [http://www.gnu.org/software/gsl/manual/html_node/Multidimensional-Minimization.html GSL 'multimin'] (GPL) several multidimensional dense-matrix unconstrained optimisation methods including conjugate gradient methods, quasi-newton methods, steepest descent and Nelder-Mead simplex method.
* [http://acts.nersc.gov/opt++/index.html OPT++] (free, includes ''optional'' wrapping of non-free NPSOL). Good but dense matrices only (RPS). Superceded by MOOCHO?
* [http://software.sandia.gov/appspack/version5.0/index.html APPSPACK] (GPL?) 'asynchronous parallel generating set search', derivative-free.
* [http://www.eng.buffalo.edu/Research/MODEL/mdo.test.orig/CONMIN/ CONMIN] ('free' but where from?) 'two-step limited memory quasi Newton like Conjugate Gradient method with Beale restarts'.
* [http://www.cs.sandia.gov/SGOPT/ SGOPT] (LGPL) Evolutionary and pattern-search algorithms
* [http://www.math.ufl.edu/~hager/ OPTPACK] (PD) 'a dual algorithm for constrained optimization'
* [http://www.netlib.org/minpack/ MINPACK] (BSD-like) unconstrained
* [http://www.coin-or.org/Bonmin/ BonMin] (CPL) Part of the COIN-OR suite; a solver for convect MINLP problems.
* [https://projects.coin-or.org/Couenne Couenne] (CPL) Part of the COIN-OR suite; a solver for non-convex MINLP problems.
* [http://www.ime.usp.br/~egbirgin/tango/ ALGENCAN] (GPL) Augmented Lagrangian plus an embedded smooth function box-constraint solver called 'GENCAN'
* [http://www.ime.usp.br/~egbirgin/tango/ SPG] (GPL) for smooth function with convex constraint
* [http://www.gerad.ca/~couturgi/NOMAD/ NOMAD] (GPL) Generalized Pattern Search (GPS) algorithms to solve nonlinear optimization problems
* [http://www-fp.mcs.anl.gov/otc/Tools/LBFGS-B/ LBFGS-B] (PD?) limited-memory quasi-Newton code
* [http://ab-initio.mit.edu/wiki/index.php/NLopt NLopt] (LGPL) wrapper for a few other FOSS codes, but also reportedly has some new implementations of certain algorithms
* [http://www.uni-graz.at/imawww/kuntsevich/solvopt/ SolvOpt] (PD) 'method of exact penalisation', based on N.Z. Shor r-algorithm
* [http://openopt.org/ralg ralg] (BSD) - an implementation of N.Z. Shor r-algorithm; nonlinear/nonsmooth constrained/unconstrained problems

'''Metaheuristics'''

* [https://code.google.com/p/popot/ popot] (new BSD license) a C++ Template based library for population based optimization. It includes various population-based optimization algorithms such as particle swarm, ant colonies, evolutionary strategies.
* [http://dev.heuristiclab.com/ HeuristicLab] (GPL) a framework for heuristic and evolutionary algorithms developed by Heuristic and Evolutionary Algorithms Laboratory (HEAL)
* [http://gundog.lbl.gov/GO/index.html GenOpt] (modified BSD license) an optimization program for the minimization of a cost function that is evaluated by an external simulation program, developed by Berkley Lab and written in Java
* [http://jswarm-pso.sourceforge.net/ JSwarm-PSO] (GPL) a Particle swarm optimization package written in Java

'''Wrappers'''

* [http://www.coin-or.org/NLPAPI/index.html NLPAPI] (GPL?) a generalised wrapper for NLP solvers, including support for LANCELOT.
* [https://projects.coin-or.org/GAMSlinks/ GAMSlinks] (GPL?) a wrapper for [https://projects.coin-or.org/ COIN-OR] solvers that allows them to be called from GAMS. This is interesting as it shows how we could implement set up ASCEND so that it can use GAMS solvers, which adapting FOSS solvers that run under GAMS much easier to adapt for use with ASCEND.
* [http://www.netlib.org/ampl/solvers/lancelot/ AMPL/LANCELOT] a wrapper for running LANCELOT from AMPL. Again, this provides a way for seeing how solvers that have been adapted for use in AMPL might be also be connected to from ASCEND.
* [http://cuter.rl.ac.uk/cuter-www/interfaces.html CUTEr] (GPL-like license) is a wrapper for a wide range of optimisation solvers, and also a testing framework.
* [https://projects.coin-or.org/Osi OSI] (CPL?) wrapper for quite a wide range of LP solvers, from COIN-OR.
* [https://projects.coin-or.org/OS OS] (CPL?) Optimisation Services, a number of interface languages and APIs for communicating between problem 'servers' and solver 'clients', with support for a range of COIN-OR solvers and converters for GAMS/AMPL input files.
* [http://wiki.services.openoffice.org/wiki/Optimization_Solver OpenOffice.org's Solver]
* [http://openopt.org OpenOpt] (BSD) a general purpose optimization framework written in Python and NumPy, capable of automatic differentiation.
* [http://code.google.com/p/pulp-or/ PuLP] (MIT license) a Python interface for expressing and solving [[LP]] problems.
* [http://rima.incremental.co.nz/ RIMA] (MIT license) a Lua interface for expressing and solving [[LP]] and [[MILP]] problems using CBC, CLP and lpsolve.

'''Unknown:'''

* [http://coool.mines.edu/ COOOL]

Another free list: [http://software.sandia.gov/Acro/html/Main/AcroPackages.html]

There are some more listed in the [ftp://rtfm.mit.edu/pub/usenet/sci.answers/nonlinear-programming-faq nonlinear-programming-faq].

== Free for non-commercial use ==

Trust region

* [http://www.numerical.rl.ac.uk/lancelot/blurb.html LANCELOT] (no redistribution or resale) Trust region method, adapt for bound constraints

Active set

* [http://www-unix.mcs.anl.gov/~more/tron/ TRON] (permission to copy and modify, but only to be used for 'internal research' ([http://plato.asu.edu/ftp/other_software/tron_f90.tar.gz download]) active set method that uses a combination of gradient projections and a preconditioned conjugate gradient method to minimize an objective function. TRON only provides for 'box' constraints and has no support for equality constraints, although it may be possible to add support for that by wrapping TRON around an NLA solver?

Sequential quadratic programming

* [http://plato.la.asu.edu/donlp2.html DONLP2] (dense; free for non-commercial purposes)

== Some proprietary alternatives ==

Generalised reduced gradient method:

* [[CONOPT]] (plus others in certain cases)
* [http://www.sbsi-sol-optimize.com/asp/sol_product_minos.htm MINOS] (uses GRG for linear constraints, else 'sparse SLC algorithm (a projected Lagrangian method, related to Robinson's method)' for nonlinear constraints. Used when gradient evaluation is cheap.
* MS Excel [http://support.microsoft.com/kb/q214115/ Solver].
* GRG2
* LSGRG2
* [http://www.pinterconsulting.com/ LGO] 'Lipschitz Global Optimizer'

Sequential quadratic programming:

* [http://www.sbsi-sol-optimize.com/asp/sol_products_snopt_desc.htm SNOPT] (sparse) Used when gradient evaluation is expensive. 'SNOPT employs a sparse SQP algorithm with limited-memory quasi-Newton approximations to the Hessian of Lagrangian. An augmented Lagrangian merit function promotes convergence from an arbitrary point.'
* [http://www.uni-bayreuth.de/departments/math/~kschittkowski/nlpqlp22.htm NLPQLP]
* [http://www.sbsi-sol-optimize.com/asp/sol_product_npsol.htm NPSOL]
* [http://www.sbsi-sol-optimize.com/asp/sol_lssol105description.htm LSSOL] (dense, 'two-phase (primal) quadratic programming')
* [http://www.princeton.edu/~rvdb/ LOQO] (free 30-day trial) 'LOQO is based on an infeasible, primal-dual, interior-point method applied to a sequence of quadratic approximations to the given problem'
* [http://www.mcs.anl.gov/~leyffer/solvers.html FilterSQP]

Active set method:

* [http://www.sbsi-sol-optimize.com/asp/sol_product_qpopt.htm QPOPT] (dense)

Other methods:

* [http://www.ziena.com/knitro.htm KNITRO] (three methods: interior point direct, interior point conjugate gradient, 'active set')
* [http://www.gams.com/dd/docs/solvers/pathnlp.pdf PATHNLP]. 'PATHNLP solves an NLP by internally constructing the Karush-Kuhn-Tucker (KKT) system of first-order optimality conditions associated with the NLP and solving this system using the PATH solver for complementarity problems'. Supposedly good for convex problems.
* [http://www.mosek.com/products.html MOSEK] (limited version available for download, or free student license) Interior point method plus simplex method.
* [http://www2.am.uni-erlangen.de/~kocvara/pennon/ PENNON] 'penalty method', 'PBM method of Ben-Tal and Zibulevsky'

Global optimisation

* [http://www.andrew.cmu.edu/user/ns1b/baron/baron.html BARON]
* [http://www.ganso.com.au/index.php GANSO]

Methods not yet checked:

* IMSL and NAG software libraries
''More to come''

Mixed integer/nonlinear programs:

* [http://www.gams.com/solvers/solvers.htm#DICOPT DICOPT]: MINLP

See also [[Survey of sparse matrix software]]

[[Category:Development]]
[[Category:Miscellany]]

Survey of optimisation software

2015-08-11T09:43:15Z

Dimitris: /* Free Open Source Software options */

The following is a survey of optimisation software that was performed as a part of our effort to identify options for a [[Non-proprietary Optimisation]] solver for ASCEND. Feel free to add any that we've missed.

== List of Lists ==

* List of NLP solvers: http://www.ici.ro/camo/hnp.htm
* List of unconstrained optimisation solvers: http://www.ici.ro/camo/huo.htm
* There ''was'' a nice list at http://www.scicomp.uni-erlangen.de/SW/opt.html but the link seems to be broken at the moment.
* 'Decision tree' for optimization software http://plato.asu.edu/sub/nlores.html
* Description of different types of optimisation problems: http://coool.mines.edu/report/node3.html

== Free Open Source Software options ==

* [https://projects.coin-or.org/Ipopt IPOPT] (LGPL) 'Interior-Point Filter Line-Search Algorithm'. Possibly some problems with scaling of variables (according to RPS). can use a number of free and non-free matrix solvers; the free matrix solver in version 3.3.1 is MUMPS. See also [[IPOPT]] in this wiki.
* [http://trilinos.sandia.gov/packages/moocho/ MOOCHO] (GPL?) reduced sequential quadratic programming (SQP); allows the user to supply their own linear solver.
* [http://www.gnu.org/software/gsl/manual/html_node/Multidimensional-Minimization.html GSL 'multimin'] (GPL) several multidimensional dense-matrix unconstrained optimisation methods including conjugate gradient methods, quasi-newton methods, steepest descent and Nelder-Mead simplex method.
* [http://acts.nersc.gov/opt++/index.html OPT++] (free, includes ''optional'' wrapping of non-free NPSOL). Good but dense matrices only (RPS). Superceded by MOOCHO?
* [http://software.sandia.gov/appspack/version5.0/index.html APPSPACK] (GPL?) 'asynchronous parallel generating set search', derivative-free.
* [http://www.eng.buffalo.edu/Research/MODEL/mdo.test.orig/CONMIN/ CONMIN] ('free' but where from?) 'two-step limited memory quasi Newton like Conjugate Gradient method with Beale restarts'.
* [http://www.cs.sandia.gov/SGOPT/ SGOPT] (LGPL) Evolutionary and pattern-search algorithms
* [http://www.math.ufl.edu/~hager/ OPTPACK] (PD) 'a dual algorithm for constrained optimization'
* [http://www.netlib.org/minpack/ MINPACK] (BSD-like) unconstrained
* [http://www.coin-or.org/Bonmin/ BonMin] (CPL) Part of the COIN-OR suite; a solver for convect MINLP problems.
* [https://projects.coin-or.org/Couenne Couenne] (CPL) Part of the COIN-OR suite; a solver for non-convex MINLP problems.
* [http://www.ime.usp.br/~egbirgin/tango/ ALGENCAN] (GPL) Augmented Lagrangian plus an embedded smooth function box-constraint solver called 'GENCAN'
* [http://www.ime.usp.br/~egbirgin/tango/ SPG] (GPL) for smooth function with convex constraint
* [http://www.gerad.ca/~couturgi/NOMAD/ NOMAD] (GPL) Generalized Pattern Search (GPS) algorithms to solve nonlinear optimization problems
* [http://www-fp.mcs.anl.gov/otc/Tools/LBFGS-B/ LBFGS-B] (PD?) limited-memory quasi-Newton code
* [http://ab-initio.mit.edu/wiki/index.php/NLopt NLopt] (LGPL) wrapper for a few other FOSS codes, but also reportedly has some new implementations of certain algorithms
* [http://www.uni-graz.at/imawww/kuntsevich/solvopt/ SolvOpt] (PD) 'method of exact penalisation', based on N.Z. Shor r-algorithm
* [http://openopt.org/ralg ralg] (BSD) - an implementation of N.Z. Shor r-algorithm; nonlinear/nonsmooth constrained/unconstrained problems

'''Metaheuristics'''

* [https://code.google.com/p/popot/ popot] (new BSD license) a C++ Template based library for population based optimization. It includes various population-based optimization algorithms such as
particle swarm, ant colonies, evolutionary strategies.
* [http://dev.heuristiclab.com/ HeuristicLab] (GPL) a framework for heuristic and evolutionary algorithms developed by Heuristic and Evolutionary Algorithms Laboratory (HEAL)
* [http://gundog.lbl.gov/GO/index.html GenOpt] (modified BSD license) an optimization program for the minimization of a cost function that is evaluated by an external simulation program, developed by Berkley Lab and written in Java
* [http://jswarm-pso.sourceforge.net/ JSwarm-PSO] (GPL) a Particle swarm optimization package written in Java

'''Wrappers'''

* [http://www.coin-or.org/NLPAPI/index.html NLPAPI] (GPL?) a generalised wrapper for NLP solvers, including support for LANCELOT.
* [https://projects.coin-or.org/GAMSlinks/ GAMSlinks] (GPL?) a wrapper for [https://projects.coin-or.org/ COIN-OR] solvers that allows them to be called from GAMS. This is interesting as it shows how we could implement set up ASCEND so that it can use GAMS solvers, which adapting FOSS solvers that run under GAMS much easier to adapt for use with ASCEND.
* [http://www.netlib.org/ampl/solvers/lancelot/ AMPL/LANCELOT] a wrapper for running LANCELOT from AMPL. Again, this provides a way for seeing how solvers that have been adapted for use in AMPL might be also be connected to from ASCEND.
* [http://cuter.rl.ac.uk/cuter-www/interfaces.html CUTEr] (GPL-like license) is a wrapper for a wide range of optimisation solvers, and also a testing framework.
* [https://projects.coin-or.org/Osi OSI] (CPL?) wrapper for quite a wide range of LP solvers, from COIN-OR.
* [https://projects.coin-or.org/OS OS] (CPL?) Optimisation Services, a number of interface languages and APIs for communicating between problem 'servers' and solver 'clients', with support for a range of COIN-OR solvers and converters for GAMS/AMPL input files.
* [http://wiki.services.openoffice.org/wiki/Optimization_Solver OpenOffice.org's Solver]
* [http://openopt.org OpenOpt] (BSD) a general purpose optimization framework written in Python and NumPy, capable of automatic differentiation.
* [http://code.google.com/p/pulp-or/ PuLP] (MIT license) a Python interface for expressing and solving [[LP]] problems.
* [http://rima.incremental.co.nz/ RIMA] (MIT license) a Lua interface for expressing and solving [[LP]] and [[MILP]] problems using CBC, CLP and lpsolve.

'''Unknown:'''

* [http://coool.mines.edu/ COOOL]

Another free list: [http://software.sandia.gov/Acro/html/Main/AcroPackages.html]

There are some more listed in the [ftp://rtfm.mit.edu/pub/usenet/sci.answers/nonlinear-programming-faq nonlinear-programming-faq].

== Free for non-commercial use ==

Trust region

* [http://www.numerical.rl.ac.uk/lancelot/blurb.html LANCELOT] (no redistribution or resale) Trust region method, adapt for bound constraints

Active set

* [http://www-unix.mcs.anl.gov/~more/tron/ TRON] (permission to copy and modify, but only to be used for 'internal research' ([http://plato.asu.edu/ftp/other_software/tron_f90.tar.gz download]) active set method that uses a combination of gradient projections and a preconditioned conjugate gradient method to minimize an objective function. TRON only provides for 'box' constraints and has no support for equality constraints, although it may be possible to add support for that by wrapping TRON around an NLA solver?

Sequential quadratic programming

* [http://plato.la.asu.edu/donlp2.html DONLP2] (dense; free for non-commercial purposes)

== Some proprietary alternatives ==

Generalised reduced gradient method:

* [[CONOPT]] (plus others in certain cases)
* [http://www.sbsi-sol-optimize.com/asp/sol_product_minos.htm MINOS] (uses GRG for linear constraints, else 'sparse SLC algorithm (a projected Lagrangian method, related to Robinson's method)' for nonlinear constraints. Used when gradient evaluation is cheap.
* MS Excel [http://support.microsoft.com/kb/q214115/ Solver].
* GRG2
* LSGRG2
* [http://www.pinterconsulting.com/ LGO] 'Lipschitz Global Optimizer'

Sequential quadratic programming:

* [http://www.sbsi-sol-optimize.com/asp/sol_products_snopt_desc.htm SNOPT] (sparse) Used when gradient evaluation is expensive. 'SNOPT employs a sparse SQP algorithm with limited-memory quasi-Newton approximations to the Hessian of Lagrangian. An augmented Lagrangian merit function promotes convergence from an arbitrary point.'
* [http://www.uni-bayreuth.de/departments/math/~kschittkowski/nlpqlp22.htm NLPQLP]
* [http://www.sbsi-sol-optimize.com/asp/sol_product_npsol.htm NPSOL]
* [http://www.sbsi-sol-optimize.com/asp/sol_lssol105description.htm LSSOL] (dense, 'two-phase (primal) quadratic programming')
* [http://www.princeton.edu/~rvdb/ LOQO] (free 30-day trial) 'LOQO is based on an infeasible, primal-dual, interior-point method applied to a sequence of quadratic approximations to the given problem'
* [http://www.mcs.anl.gov/~leyffer/solvers.html FilterSQP]

Active set method:

* [http://www.sbsi-sol-optimize.com/asp/sol_product_qpopt.htm QPOPT] (dense)

Other methods:

* [http://www.ziena.com/knitro.htm KNITRO] (three methods: interior point direct, interior point conjugate gradient, 'active set')
* [http://www.gams.com/dd/docs/solvers/pathnlp.pdf PATHNLP]. 'PATHNLP solves an NLP by internally constructing the Karush-Kuhn-Tucker (KKT) system of first-order optimality conditions associated with the NLP and solving this system using the PATH solver for complementarity problems'. Supposedly good for convex problems.
* [http://www.mosek.com/products.html MOSEK] (limited version available for download, or free student license) Interior point method plus simplex method.
* [http://www2.am.uni-erlangen.de/~kocvara/pennon/ PENNON] 'penalty method', 'PBM method of Ben-Tal and Zibulevsky'

Global optimisation

* [http://www.andrew.cmu.edu/user/ns1b/baron/baron.html BARON]
* [http://www.ganso.com.au/index.php GANSO]

Methods not yet checked:

* IMSL and NAG software libraries
''More to come''

Mixed integer/nonlinear programs:

* [http://www.gams.com/solvers/solvers.htm#DICOPT DICOPT]: MINLP

See also [[Survey of sparse matrix software]]

[[Category:Development]]
[[Category:Miscellany]]

Survey of optimisation software

2015-08-11T09:35:23Z

Dimitris: /* Free Open Source Software options */

The following is a survey of optimisation software that was performed as a part of our effort to identify options for a [[Non-proprietary Optimisation]] solver for ASCEND. Feel free to add any that we've missed.

== List of Lists ==

* List of NLP solvers: http://www.ici.ro/camo/hnp.htm
* List of unconstrained optimisation solvers: http://www.ici.ro/camo/huo.htm
* There ''was'' a nice list at http://www.scicomp.uni-erlangen.de/SW/opt.html but the link seems to be broken at the moment.
* 'Decision tree' for optimization software http://plato.asu.edu/sub/nlores.html
* Description of different types of optimisation problems: http://coool.mines.edu/report/node3.html

== Free Open Source Software options ==

* [https://projects.coin-or.org/Ipopt IPOPT] (LGPL) 'Interior-Point Filter Line-Search Algorithm'. Possibly some problems with scaling of variables (according to RPS). can use a number of free and non-free matrix solvers; the free matrix solver in version 3.3.1 is MUMPS. See also [[IPOPT]] in this wiki.
* [http://trilinos.sandia.gov/packages/moocho/ MOOCHO] (GPL?) reduced sequential quadratic programming (SQP); allows the user to supply their own linear solver.
* [http://www.gnu.org/software/gsl/manual/html_node/Multidimensional-Minimization.html GSL 'multimin'] (GPL) several multidimensional dense-matrix unconstrained optimisation methods including conjugate gradient methods, quasi-newton methods, steepest descent and Nelder-Mead simplex method.
* [http://acts.nersc.gov/opt++/index.html OPT++] (free, includes ''optional'' wrapping of non-free NPSOL). Good but dense matrices only (RPS). Superceded by MOOCHO?
* [http://software.sandia.gov/appspack/version5.0/index.html APPSPACK] (GPL?) 'asynchronous parallel generating set search', derivative-free.
* [http://www.eng.buffalo.edu/Research/MODEL/mdo.test.orig/CONMIN/ CONMIN] ('free' but where from?) 'two-step limited memory quasi Newton like Conjugate Gradient method with Beale restarts'.
* [http://www.cs.sandia.gov/SGOPT/ SGOPT] (LGPL) Evolutionary and pattern-search algorithms
* [http://www.math.ufl.edu/~hager/ OPTPACK] (PD) 'a dual algorithm for constrained optimization'
* [http://www.netlib.org/minpack/ MINPACK] (BSD-like) unconstrained
* [http://www.coin-or.org/Bonmin/ BonMin] (CPL) Part of the COIN-OR suite; a solver for convect MINLP problems.
* [https://projects.coin-or.org/Couenne Couenne] (CPL) Part of the COIN-OR suite; a solver for non-convex MINLP problems.
* [http://www.ime.usp.br/~egbirgin/tango/ ALGENCAN] (GPL) Augmented Lagrangian plus an embedded smooth function box-constraint solver called 'GENCAN'
* [http://www.ime.usp.br/~egbirgin/tango/ SPG] (GPL) for smooth function with convex constraint
* [http://www.gerad.ca/~couturgi/NOMAD/ NOMAD] (GPL) Generalized Pattern Search (GPS) algorithms to solve nonlinear optimization problems
* [http://www-fp.mcs.anl.gov/otc/Tools/LBFGS-B/ LBFGS-B] (PD?) limited-memory quasi-Newton code
* [http://ab-initio.mit.edu/wiki/index.php/NLopt NLopt] (LGPL) wrapper for a few other FOSS codes, but also reportedly has some new implementations of certain algorithms
* [http://www.uni-graz.at/imawww/kuntsevich/solvopt/ SolvOpt] (PD) 'method of exact penalisation', based on N.Z. Shor r-algorithm
* [http://openopt.org/ralg ralg] (BSD) - an implementation of N.Z. Shor r-algorithm; nonlinear/nonsmooth constrained/unconstrained problems

'''Metaheuristics'''
* [http://dev.heuristiclab.com/ HeuristicLab] (GPL) a framework for heuristic and evolutionary algorithms developed by Heuristic and Evolutionary Algorithms Laboratory (HEAL)
* [http://gundog.lbl.gov/GO/index.html GenOpt] (modified BSD license) an optimization program for the minimization of a cost function that is evaluated by an external simulation program, developed by Berkley Lab and written in Java
* [http://jswarm-pso.sourceforge.net/ JSwarm-PSO] (GPL) a Particle swarm optimization package written in Java

'''Wrappers'''

* [http://www.coin-or.org/NLPAPI/index.html NLPAPI] (GPL?) a generalised wrapper for NLP solvers, including support for LANCELOT.
* [https://projects.coin-or.org/GAMSlinks/ GAMSlinks] (GPL?) a wrapper for [https://projects.coin-or.org/ COIN-OR] solvers that allows them to be called from GAMS. This is interesting as it shows how we could implement set up ASCEND so that it can use GAMS solvers, which adapting FOSS solvers that run under GAMS much easier to adapt for use with ASCEND.
* [http://www.netlib.org/ampl/solvers/lancelot/ AMPL/LANCELOT] a wrapper for running LANCELOT from AMPL. Again, this provides a way for seeing how solvers that have been adapted for use in AMPL might be also be connected to from ASCEND.
* [http://cuter.rl.ac.uk/cuter-www/interfaces.html CUTEr] (GPL-like license) is a wrapper for a wide range of optimisation solvers, and also a testing framework.
* [https://projects.coin-or.org/Osi OSI] (CPL?) wrapper for quite a wide range of LP solvers, from COIN-OR.
* [https://projects.coin-or.org/OS OS] (CPL?) Optimisation Services, a number of interface languages and APIs for communicating between problem 'servers' and solver 'clients', with support for a range of COIN-OR solvers and converters for GAMS/AMPL input files.
* [http://wiki.services.openoffice.org/wiki/Optimization_Solver OpenOffice.org's Solver]
* [http://openopt.org OpenOpt] (BSD) a general purpose optimization framework written in Python and NumPy, capable of automatic differentiation.
* [http://code.google.com/p/pulp-or/ PuLP] (MIT license) a Python interface for expressing and solving [[LP]] problems.
* [http://rima.incremental.co.nz/ RIMA] (MIT license) a Lua interface for expressing and solving [[LP]] and [[MILP]] problems using CBC, CLP and lpsolve.

'''Unknown:'''

* [http://coool.mines.edu/ COOOL]

Another free list: [http://software.sandia.gov/Acro/html/Main/AcroPackages.html]

There are some more listed in the [ftp://rtfm.mit.edu/pub/usenet/sci.answers/nonlinear-programming-faq nonlinear-programming-faq].

== Free for non-commercial use ==

Trust region

* [http://www.numerical.rl.ac.uk/lancelot/blurb.html LANCELOT] (no redistribution or resale) Trust region method, adapt for bound constraints

Active set

* [http://www-unix.mcs.anl.gov/~more/tron/ TRON] (permission to copy and modify, but only to be used for 'internal research' ([http://plato.asu.edu/ftp/other_software/tron_f90.tar.gz download]) active set method that uses a combination of gradient projections and a preconditioned conjugate gradient method to minimize an objective function. TRON only provides for 'box' constraints and has no support for equality constraints, although it may be possible to add support for that by wrapping TRON around an NLA solver?

Sequential quadratic programming

* [http://plato.la.asu.edu/donlp2.html DONLP2] (dense; free for non-commercial purposes)

== Some proprietary alternatives ==

Generalised reduced gradient method:

* [[CONOPT]] (plus others in certain cases)
* [http://www.sbsi-sol-optimize.com/asp/sol_product_minos.htm MINOS] (uses GRG for linear constraints, else 'sparse SLC algorithm (a projected Lagrangian method, related to Robinson's method)' for nonlinear constraints. Used when gradient evaluation is cheap.
* MS Excel [http://support.microsoft.com/kb/q214115/ Solver].
* GRG2
* LSGRG2
* [http://www.pinterconsulting.com/ LGO] 'Lipschitz Global Optimizer'

Sequential quadratic programming:

* [http://www.sbsi-sol-optimize.com/asp/sol_products_snopt_desc.htm SNOPT] (sparse) Used when gradient evaluation is expensive. 'SNOPT employs a sparse SQP algorithm with limited-memory quasi-Newton approximations to the Hessian of Lagrangian. An augmented Lagrangian merit function promotes convergence from an arbitrary point.'
* [http://www.uni-bayreuth.de/departments/math/~kschittkowski/nlpqlp22.htm NLPQLP]
* [http://www.sbsi-sol-optimize.com/asp/sol_product_npsol.htm NPSOL]
* [http://www.sbsi-sol-optimize.com/asp/sol_lssol105description.htm LSSOL] (dense, 'two-phase (primal) quadratic programming')
* [http://www.princeton.edu/~rvdb/ LOQO] (free 30-day trial) 'LOQO is based on an infeasible, primal-dual, interior-point method applied to a sequence of quadratic approximations to the given problem'
* [http://www.mcs.anl.gov/~leyffer/solvers.html FilterSQP]

Active set method:

* [http://www.sbsi-sol-optimize.com/asp/sol_product_qpopt.htm QPOPT] (dense)

Other methods:

* [http://www.ziena.com/knitro.htm KNITRO] (three methods: interior point direct, interior point conjugate gradient, 'active set')
* [http://www.gams.com/dd/docs/solvers/pathnlp.pdf PATHNLP]. 'PATHNLP solves an NLP by internally constructing the Karush-Kuhn-Tucker (KKT) system of first-order optimality conditions associated with the NLP and solving this system using the PATH solver for complementarity problems'. Supposedly good for convex problems.
* [http://www.mosek.com/products.html MOSEK] (limited version available for download, or free student license) Interior point method plus simplex method.
* [http://www2.am.uni-erlangen.de/~kocvara/pennon/ PENNON] 'penalty method', 'PBM method of Ben-Tal and Zibulevsky'

Global optimisation

* [http://www.andrew.cmu.edu/user/ns1b/baron/baron.html BARON]
* [http://www.ganso.com.au/index.php GANSO]

Methods not yet checked:

* IMSL and NAG software libraries
''More to come''

Mixed integer/nonlinear programs:

* [http://www.gams.com/solvers/solvers.htm#DICOPT DICOPT]: MINLP

See also [[Survey of sparse matrix software]]

[[Category:Development]]
[[Category:Miscellany]]

Survey of optimisation software

2015-08-11T09:35:08Z

Dimitris: /* Free Open Source Software options */

The following is a survey of optimisation software that was performed as a part of our effort to identify options for a [[Non-proprietary Optimisation]] solver for ASCEND. Feel free to add any that we've missed.

== List of Lists ==

* List of NLP solvers: http://www.ici.ro/camo/hnp.htm
* List of unconstrained optimisation solvers: http://www.ici.ro/camo/huo.htm
* There ''was'' a nice list at http://www.scicomp.uni-erlangen.de/SW/opt.html but the link seems to be broken at the moment.
* 'Decision tree' for optimization software http://plato.asu.edu/sub/nlores.html
* Description of different types of optimisation problems: http://coool.mines.edu/report/node3.html

== Free Open Source Software options ==

* [https://projects.coin-or.org/Ipopt IPOPT] (LGPL) 'Interior-Point Filter Line-Search Algorithm'. Possibly some problems with scaling of variables (according to RPS). can use a number of free and non-free matrix solvers; the free matrix solver in version 3.3.1 is MUMPS. See also [[IPOPT]] in this wiki.
* [http://trilinos.sandia.gov/packages/moocho/ MOOCHO] (GPL?) reduced sequential quadratic programming (SQP); allows the user to supply their own linear solver.
* [http://www.gnu.org/software/gsl/manual/html_node/Multidimensional-Minimization.html GSL 'multimin'] (GPL) several multidimensional dense-matrix unconstrained optimisation methods including conjugate gradient methods, quasi-newton methods, steepest descent and Nelder-Mead simplex method.
* [http://acts.nersc.gov/opt++/index.html OPT++] (free, includes ''optional'' wrapping of non-free NPSOL). Good but dense matrices only (RPS). Superceded by MOOCHO?
* [http://software.sandia.gov/appspack/version5.0/index.html APPSPACK] (GPL?) 'asynchronous parallel generating set search', derivative-free.
* [http://www.eng.buffalo.edu/Research/MODEL/mdo.test.orig/CONMIN/ CONMIN] ('free' but where from?) 'two-step limited memory quasi Newton like Conjugate Gradient method with Beale restarts'.
* [http://www.cs.sandia.gov/SGOPT/ SGOPT] (LGPL) Evolutionary and pattern-search algorithms
* [http://www.math.ufl.edu/~hager/ OPTPACK] (PD) 'a dual algorithm for constrained optimization'
* [http://www.netlib.org/minpack/ MINPACK] (BSD-like) unconstrained
* [http://www.coin-or.org/Bonmin/ BonMin] (CPL) Part of the COIN-OR suite; a solver for convect MINLP problems.
* [https://projects.coin-or.org/Couenne Couenne] (CPL) Part of the COIN-OR suite; a solver for non-convex MINLP problems.
* [http://www.ime.usp.br/~egbirgin/tango/ ALGENCAN] (GPL) Augmented Lagrangian plus an embedded smooth function box-constraint solver called 'GENCAN'
* [http://www.ime.usp.br/~egbirgin/tango/ SPG] (GPL) for smooth function with convex constraint
* [http://www.gerad.ca/~couturgi/NOMAD/ NOMAD] (GPL) Generalized Pattern Search (GPS) algorithms to solve nonlinear optimization problems
* [http://www-fp.mcs.anl.gov/otc/Tools/LBFGS-B/ LBFGS-B] (PD?) limited-memory quasi-Newton code
* [http://ab-initio.mit.edu/wiki/index.php/NLopt NLopt] (LGPL) wrapper for a few other FOSS codes, but also reportedly has some new implementations of certain algorithms
* [http://www.uni-graz.at/imawww/kuntsevich/solvopt/ SolvOpt] (PD) 'method of exact penalisation', based on N.Z. Shor r-algorithm
* [http://openopt.org/ralg ralg] (BSD) - an implementation of N.Z. Shor r-algorithm; nonlinear/nonsmooth constrained/unconstrained problems

'''Metaheuristics'''
* [http://dev.heuristiclab.com/ HeuristicLab] (GPL) a framework for heuristic and evolutionary algorithms developed by Heuristic and Evolutionary Algorithms Laboratory (HEAL)
* [hhttp://gundog.lbl.gov/GO/index.html GenOpt] (modified BSD license) an optimization program for the minimization of a cost function that is evaluated by an external simulation program, developed by Berkley Lab and written in Java
* [http://jswarm-pso.sourceforge.net/ JSwarm-PSO] (GPL) a Particle swarm optimization package written in Java

'''Wrappers'''

* [http://www.coin-or.org/NLPAPI/index.html NLPAPI] (GPL?) a generalised wrapper for NLP solvers, including support for LANCELOT.
* [https://projects.coin-or.org/GAMSlinks/ GAMSlinks] (GPL?) a wrapper for [https://projects.coin-or.org/ COIN-OR] solvers that allows them to be called from GAMS. This is interesting as it shows how we could implement set up ASCEND so that it can use GAMS solvers, which adapting FOSS solvers that run under GAMS much easier to adapt for use with ASCEND.
* [http://www.netlib.org/ampl/solvers/lancelot/ AMPL/LANCELOT] a wrapper for running LANCELOT from AMPL. Again, this provides a way for seeing how solvers that have been adapted for use in AMPL might be also be connected to from ASCEND.
* [http://cuter.rl.ac.uk/cuter-www/interfaces.html CUTEr] (GPL-like license) is a wrapper for a wide range of optimisation solvers, and also a testing framework.
* [https://projects.coin-or.org/Osi OSI] (CPL?) wrapper for quite a wide range of LP solvers, from COIN-OR.
* [https://projects.coin-or.org/OS OS] (CPL?) Optimisation Services, a number of interface languages and APIs for communicating between problem 'servers' and solver 'clients', with support for a range of COIN-OR solvers and converters for GAMS/AMPL input files.
* [http://wiki.services.openoffice.org/wiki/Optimization_Solver OpenOffice.org's Solver]
* [http://openopt.org OpenOpt] (BSD) a general purpose optimization framework written in Python and NumPy, capable of automatic differentiation.
* [http://code.google.com/p/pulp-or/ PuLP] (MIT license) a Python interface for expressing and solving [[LP]] problems.
* [http://rima.incremental.co.nz/ RIMA] (MIT license) a Lua interface for expressing and solving [[LP]] and [[MILP]] problems using CBC, CLP and lpsolve.

'''Unknown:'''

* [http://coool.mines.edu/ COOOL]

Another free list: [http://software.sandia.gov/Acro/html/Main/AcroPackages.html]

There are some more listed in the [ftp://rtfm.mit.edu/pub/usenet/sci.answers/nonlinear-programming-faq nonlinear-programming-faq].

== Free for non-commercial use ==

Trust region

* [http://www.numerical.rl.ac.uk/lancelot/blurb.html LANCELOT] (no redistribution or resale) Trust region method, adapt for bound constraints

Active set

* [http://www-unix.mcs.anl.gov/~more/tron/ TRON] (permission to copy and modify, but only to be used for 'internal research' ([http://plato.asu.edu/ftp/other_software/tron_f90.tar.gz download]) active set method that uses a combination of gradient projections and a preconditioned conjugate gradient method to minimize an objective function. TRON only provides for 'box' constraints and has no support for equality constraints, although it may be possible to add support for that by wrapping TRON around an NLA solver?

Sequential quadratic programming

* [http://plato.la.asu.edu/donlp2.html DONLP2] (dense; free for non-commercial purposes)

== Some proprietary alternatives ==

Generalised reduced gradient method:

* [[CONOPT]] (plus others in certain cases)
* [http://www.sbsi-sol-optimize.com/asp/sol_product_minos.htm MINOS] (uses GRG for linear constraints, else 'sparse SLC algorithm (a projected Lagrangian method, related to Robinson's method)' for nonlinear constraints. Used when gradient evaluation is cheap.
* MS Excel [http://support.microsoft.com/kb/q214115/ Solver].
* GRG2
* LSGRG2
* [http://www.pinterconsulting.com/ LGO] 'Lipschitz Global Optimizer'

Sequential quadratic programming:

* [http://www.sbsi-sol-optimize.com/asp/sol_products_snopt_desc.htm SNOPT] (sparse) Used when gradient evaluation is expensive. 'SNOPT employs a sparse SQP algorithm with limited-memory quasi-Newton approximations to the Hessian of Lagrangian. An augmented Lagrangian merit function promotes convergence from an arbitrary point.'
* [http://www.uni-bayreuth.de/departments/math/~kschittkowski/nlpqlp22.htm NLPQLP]
* [http://www.sbsi-sol-optimize.com/asp/sol_product_npsol.htm NPSOL]
* [http://www.sbsi-sol-optimize.com/asp/sol_lssol105description.htm LSSOL] (dense, 'two-phase (primal) quadratic programming')
* [http://www.princeton.edu/~rvdb/ LOQO] (free 30-day trial) 'LOQO is based on an infeasible, primal-dual, interior-point method applied to a sequence of quadratic approximations to the given problem'
* [http://www.mcs.anl.gov/~leyffer/solvers.html FilterSQP]

Active set method:

* [http://www.sbsi-sol-optimize.com/asp/sol_product_qpopt.htm QPOPT] (dense)

Other methods:

* [http://www.ziena.com/knitro.htm KNITRO] (three methods: interior point direct, interior point conjugate gradient, 'active set')
* [http://www.gams.com/dd/docs/solvers/pathnlp.pdf PATHNLP]. 'PATHNLP solves an NLP by internally constructing the Karush-Kuhn-Tucker (KKT) system of first-order optimality conditions associated with the NLP and solving this system using the PATH solver for complementarity problems'. Supposedly good for convex problems.
* [http://www.mosek.com/products.html MOSEK] (limited version available for download, or free student license) Interior point method plus simplex method.
* [http://www2.am.uni-erlangen.de/~kocvara/pennon/ PENNON] 'penalty method', 'PBM method of Ben-Tal and Zibulevsky'

Global optimisation

* [http://www.andrew.cmu.edu/user/ns1b/baron/baron.html BARON]
* [http://www.ganso.com.au/index.php GANSO]

Methods not yet checked:

* IMSL and NAG software libraries
''More to come''

Mixed integer/nonlinear programs:

* [http://www.gams.com/solvers/solvers.htm#DICOPT DICOPT]: MINLP

See also [[Survey of sparse matrix software]]

[[Category:Development]]
[[Category:Miscellany]]

Survey of optimisation software

2015-08-11T09:16:06Z

Dimitris: /* Free Open Source Software options */

The following is a survey of optimisation software that was performed as a part of our effort to identify options for a [[Non-proprietary Optimisation]] solver for ASCEND. Feel free to add any that we've missed.

== List of Lists ==

* List of NLP solvers: http://www.ici.ro/camo/hnp.htm
* List of unconstrained optimisation solvers: http://www.ici.ro/camo/huo.htm
* There ''was'' a nice list at http://www.scicomp.uni-erlangen.de/SW/opt.html but the link seems to be broken at the moment.
* 'Decision tree' for optimization software http://plato.asu.edu/sub/nlores.html
* Description of different types of optimisation problems: http://coool.mines.edu/report/node3.html

== Free Open Source Software options ==

* [https://projects.coin-or.org/Ipopt IPOPT] (LGPL) 'Interior-Point Filter Line-Search Algorithm'. Possibly some problems with scaling of variables (according to RPS). can use a number of free and non-free matrix solvers; the free matrix solver in version 3.3.1 is MUMPS. See also [[IPOPT]] in this wiki.
* [http://trilinos.sandia.gov/packages/moocho/ MOOCHO] (GPL?) reduced sequential quadratic programming (SQP); allows the user to supply their own linear solver.
* [http://www.gnu.org/software/gsl/manual/html_node/Multidimensional-Minimization.html GSL 'multimin'] (GPL) several multidimensional dense-matrix unconstrained optimisation methods including conjugate gradient methods, quasi-newton methods, steepest descent and Nelder-Mead simplex method.
* [http://acts.nersc.gov/opt++/index.html OPT++] (free, includes ''optional'' wrapping of non-free NPSOL). Good but dense matrices only (RPS). Superceded by MOOCHO?
* [http://software.sandia.gov/appspack/version5.0/index.html APPSPACK] (GPL?) 'asynchronous parallel generating set search', derivative-free.
* [http://www.eng.buffalo.edu/Research/MODEL/mdo.test.orig/CONMIN/ CONMIN] ('free' but where from?) 'two-step limited memory quasi Newton like Conjugate Gradient method with Beale restarts'.
* [http://www.cs.sandia.gov/SGOPT/ SGOPT] (LGPL) Evolutionary and pattern-search algorithms
* [http://www.math.ufl.edu/~hager/ OPTPACK] (PD) 'a dual algorithm for constrained optimization'
* [http://www.netlib.org/minpack/ MINPACK] (BSD-like) unconstrained
* [http://www.coin-or.org/Bonmin/ BonMin] (CPL) Part of the COIN-OR suite; a solver for convect MINLP problems.
* [https://projects.coin-or.org/Couenne Couenne] (CPL) Part of the COIN-OR suite; a solver for non-convex MINLP problems.
* [http://www.ime.usp.br/~egbirgin/tango/ ALGENCAN] (GPL) Augmented Lagrangian plus an embedded smooth function box-constraint solver called 'GENCAN'
* [http://www.ime.usp.br/~egbirgin/tango/ SPG] (GPL) for smooth function with convex constraint
* [http://www.gerad.ca/~couturgi/NOMAD/ NOMAD] (GPL) Generalized Pattern Search (GPS) algorithms to solve nonlinear optimization problems
* [http://www-fp.mcs.anl.gov/otc/Tools/LBFGS-B/ LBFGS-B] (PD?) limited-memory quasi-Newton code
* [http://ab-initio.mit.edu/wiki/index.php/NLopt NLopt] (LGPL) wrapper for a few other FOSS codes, but also reportedly has some new implementations of certain algorithms
* [http://www.uni-graz.at/imawww/kuntsevich/solvopt/ SolvOpt] (PD) 'method of exact penalisation', based on N.Z. Shor r-algorithm
* [http://openopt.org/ralg ralg] (BSD) - an implementation of N.Z. Shor r-algorithm; nonlinear/nonsmooth constrained/unconstrained problems

'''Metaheuristics'''
* [http://dev.heuristiclab.com/ HeuristicLab] (GPL) a framework for heuristic and evolutionary algorithms developed by Heuristic and Evolutionary Algorithms Laboratory (HEAL)
* [http://jswarm-pso.sourceforge.net/ JSwarm-PSO] (GPL) - a Particle swarm optimization package written in Java

'''Wrappers'''

* [http://www.coin-or.org/NLPAPI/index.html NLPAPI] (GPL?) a generalised wrapper for NLP solvers, including support for LANCELOT.
* [https://projects.coin-or.org/GAMSlinks/ GAMSlinks] (GPL?) a wrapper for [https://projects.coin-or.org/ COIN-OR] solvers that allows them to be called from GAMS. This is interesting as it shows how we could implement set up ASCEND so that it can use GAMS solvers, which adapting FOSS solvers that run under GAMS much easier to adapt for use with ASCEND.
* [http://www.netlib.org/ampl/solvers/lancelot/ AMPL/LANCELOT] a wrapper for running LANCELOT from AMPL. Again, this provides a way for seeing how solvers that have been adapted for use in AMPL might be also be connected to from ASCEND.
* [http://cuter.rl.ac.uk/cuter-www/interfaces.html CUTEr] (GPL-like license) is a wrapper for a wide range of optimisation solvers, and also a testing framework.
* [https://projects.coin-or.org/Osi OSI] (CPL?) wrapper for quite a wide range of LP solvers, from COIN-OR.
* [https://projects.coin-or.org/OS OS] (CPL?) Optimisation Services, a number of interface languages and APIs for communicating between problem 'servers' and solver 'clients', with support for a range of COIN-OR solvers and converters for GAMS/AMPL input files.
* [http://wiki.services.openoffice.org/wiki/Optimization_Solver OpenOffice.org's Solver]
* [http://openopt.org OpenOpt] (BSD) a general purpose optimization framework written in Python and NumPy, capable of automatic differentiation.
* [http://code.google.com/p/pulp-or/ PuLP] (MIT license) a Python interface for expressing and solving [[LP]] problems.
* [http://rima.incremental.co.nz/ RIMA] (MIT license) a Lua interface for expressing and solving [[LP]] and [[MILP]] problems using CBC, CLP and lpsolve.

'''Unknown:'''

* [http://coool.mines.edu/ COOOL]

Another free list: [http://software.sandia.gov/Acro/html/Main/AcroPackages.html]

There are some more listed in the [ftp://rtfm.mit.edu/pub/usenet/sci.answers/nonlinear-programming-faq nonlinear-programming-faq].

== Free for non-commercial use ==

Trust region

* [http://www.numerical.rl.ac.uk/lancelot/blurb.html LANCELOT] (no redistribution or resale) Trust region method, adapt for bound constraints

Active set

* [http://www-unix.mcs.anl.gov/~more/tron/ TRON] (permission to copy and modify, but only to be used for 'internal research' ([http://plato.asu.edu/ftp/other_software/tron_f90.tar.gz download]) active set method that uses a combination of gradient projections and a preconditioned conjugate gradient method to minimize an objective function. TRON only provides for 'box' constraints and has no support for equality constraints, although it may be possible to add support for that by wrapping TRON around an NLA solver?

Sequential quadratic programming

* [http://plato.la.asu.edu/donlp2.html DONLP2] (dense; free for non-commercial purposes)

== Some proprietary alternatives ==

Generalised reduced gradient method:

* [[CONOPT]] (plus others in certain cases)
* [http://www.sbsi-sol-optimize.com/asp/sol_product_minos.htm MINOS] (uses GRG for linear constraints, else 'sparse SLC algorithm (a projected Lagrangian method, related to Robinson's method)' for nonlinear constraints. Used when gradient evaluation is cheap.
* MS Excel [http://support.microsoft.com/kb/q214115/ Solver].
* GRG2
* LSGRG2
* [http://www.pinterconsulting.com/ LGO] 'Lipschitz Global Optimizer'

Sequential quadratic programming:

* [http://www.sbsi-sol-optimize.com/asp/sol_products_snopt_desc.htm SNOPT] (sparse) Used when gradient evaluation is expensive. 'SNOPT employs a sparse SQP algorithm with limited-memory quasi-Newton approximations to the Hessian of Lagrangian. An augmented Lagrangian merit function promotes convergence from an arbitrary point.'
* [http://www.uni-bayreuth.de/departments/math/~kschittkowski/nlpqlp22.htm NLPQLP]
* [http://www.sbsi-sol-optimize.com/asp/sol_product_npsol.htm NPSOL]
* [http://www.sbsi-sol-optimize.com/asp/sol_lssol105description.htm LSSOL] (dense, 'two-phase (primal) quadratic programming')
* [http://www.princeton.edu/~rvdb/ LOQO] (free 30-day trial) 'LOQO is based on an infeasible, primal-dual, interior-point method applied to a sequence of quadratic approximations to the given problem'
* [http://www.mcs.anl.gov/~leyffer/solvers.html FilterSQP]

Active set method:

* [http://www.sbsi-sol-optimize.com/asp/sol_product_qpopt.htm QPOPT] (dense)

Other methods:

* [http://www.ziena.com/knitro.htm KNITRO] (three methods: interior point direct, interior point conjugate gradient, 'active set')
* [http://www.gams.com/dd/docs/solvers/pathnlp.pdf PATHNLP]. 'PATHNLP solves an NLP by internally constructing the Karush-Kuhn-Tucker (KKT) system of first-order optimality conditions associated with the NLP and solving this system using the PATH solver for complementarity problems'. Supposedly good for convex problems.
* [http://www.mosek.com/products.html MOSEK] (limited version available for download, or free student license) Interior point method plus simplex method.
* [http://www2.am.uni-erlangen.de/~kocvara/pennon/ PENNON] 'penalty method', 'PBM method of Ben-Tal and Zibulevsky'

Global optimisation

* [http://www.andrew.cmu.edu/user/ns1b/baron/baron.html BARON]
* [http://www.ganso.com.au/index.php GANSO]

Methods not yet checked:

* IMSL and NAG software libraries
''More to come''

Mixed integer/nonlinear programs:

* [http://www.gams.com/solvers/solvers.htm#DICOPT DICOPT]: MINLP

See also [[Survey of sparse matrix software]]

[[Category:Development]]
[[Category:Miscellany]]

Survey of optimisation software

2015-08-11T09:15:46Z

Dimitris: /* Free Open Source Software options */

The following is a survey of optimisation software that was performed as a part of our effort to identify options for a [[Non-proprietary Optimisation]] solver for ASCEND. Feel free to add any that we've missed.

== List of Lists ==

* List of NLP solvers: http://www.ici.ro/camo/hnp.htm
* List of unconstrained optimisation solvers: http://www.ici.ro/camo/huo.htm
* There ''was'' a nice list at http://www.scicomp.uni-erlangen.de/SW/opt.html but the link seems to be broken at the moment.
* 'Decision tree' for optimization software http://plato.asu.edu/sub/nlores.html
* Description of different types of optimisation problems: http://coool.mines.edu/report/node3.html

== Free Open Source Software options ==

* [https://projects.coin-or.org/Ipopt IPOPT] (LGPL) 'Interior-Point Filter Line-Search Algorithm'. Possibly some problems with scaling of variables (according to RPS). can use a number of free and non-free matrix solvers; the free matrix solver in version 3.3.1 is MUMPS. See also [[IPOPT]] in this wiki.
* [http://trilinos.sandia.gov/packages/moocho/ MOOCHO] (GPL?) reduced sequential quadratic programming (SQP); allows the user to supply their own linear solver.
* [http://www.gnu.org/software/gsl/manual/html_node/Multidimensional-Minimization.html GSL 'multimin'] (GPL) several multidimensional dense-matrix unconstrained optimisation methods including conjugate gradient methods, quasi-newton methods, steepest descent and Nelder-Mead simplex method.
* [http://acts.nersc.gov/opt++/index.html OPT++] (free, includes ''optional'' wrapping of non-free NPSOL). Good but dense matrices only (RPS). Superceded by MOOCHO?
* [http://software.sandia.gov/appspack/version5.0/index.html APPSPACK] (GPL?) 'asynchronous parallel generating set search', derivative-free.
* [http://www.eng.buffalo.edu/Research/MODEL/mdo.test.orig/CONMIN/ CONMIN] ('free' but where from?) 'two-step limited memory quasi Newton like Conjugate Gradient method with Beale restarts'.
* [http://www.cs.sandia.gov/SGOPT/ SGOPT] (LGPL) Evolutionary and pattern-search algorithms
* [http://www.math.ufl.edu/~hager/ OPTPACK] (PD) 'a dual algorithm for constrained optimization'
* [http://www.netlib.org/minpack/ MINPACK] (BSD-like) unconstrained
* [http://www.coin-or.org/Bonmin/ BonMin] (CPL) Part of the COIN-OR suite; a solver for convect MINLP problems.
* [https://projects.coin-or.org/Couenne Couenne] (CPL) Part of the COIN-OR suite; a solver for non-convex MINLP problems.
* [http://www.ime.usp.br/~egbirgin/tango/ ALGENCAN] (GPL) Augmented Lagrangian plus an embedded smooth function box-constraint solver called 'GENCAN'
* [http://www.ime.usp.br/~egbirgin/tango/ SPG] (GPL) for smooth function with convex constraint
* [http://www.gerad.ca/~couturgi/NOMAD/ NOMAD] (GPL) Generalized Pattern Search (GPS) algorithms to solve nonlinear optimization problems
* [http://www-fp.mcs.anl.gov/otc/Tools/LBFGS-B/ LBFGS-B] (PD?) limited-memory quasi-Newton code
* [http://ab-initio.mit.edu/wiki/index.php/NLopt NLopt] (LGPL) wrapper for a few other FOSS codes, but also reportedly has some new implementations of certain algorithms
* [http://www.uni-graz.at/imawww/kuntsevich/solvopt/ SolvOpt] (PD) 'method of exact penalisation', based on N.Z. Shor r-algorithm
* [http://openopt.org/ralg ralg] (BSD) - an implementation of N.Z. Shor r-algorithm; nonlinear/nonsmooth constrained/unconstrained problems

'''Metaheuristics'''
* [http://dev.heuristiclab.com/ HeuristicLab] (GPL) a framework for heuristic and evolutionary algorithms developed by Heuristic and Evolutionary Algorithms Laboratory (HEAL)
* [http://jswarm-pso.sourceforge.net/ JSwarm-PSO] (GPL) - a Particle swarm optimization package written in Java

'''Wrappers'''

* [http://www.coin-or.org/NLPAPI/index.html NLPAPI] (GPL?) a generalised wrapper for NLP solvers, including support for LANCELOT.
* [https://projects.coin-or.org/GAMSlinks/ GAMSlinks] (GPL?) a wrapper for [https://projects.coin-or.org/ COIN-OR] solvers that allows them to be called from GAMS. This is interesting as it shows how we could implement set up ASCEND so that it can use GAMS solvers, which adapting FOSS solvers that run under GAMS much easier to adapt for use with ASCEND.
* [http://www.netlib.org/ampl/solvers/lancelot/ AMPL/LANCELOT] a wrapper for running LANCELOT from AMPL. Again, this provides a way for seeing how solvers that have been adapted for use in AMPL might be also be connected to from ASCEND.
* [http://cuter.rl.ac.uk/cuter-www/interfaces.html CUTEr] (GPL-like license) is a wrapper for a wide range of optimisation solvers, and also a testing framework.
* [https://projects.coin-or.org/Osi OSI] (CPL?) wrapper for quite a wide range of LP solvers, from COIN-OR.
* [https://projects.coin-or.org/OS OS] (CPL?) Optimisation Services, a number of interface languages and APIs for communicating between problem 'servers' and solver 'clients', with support for a range of COIN-OR solvers and converters for GAMS/AMPL input files.
* [http://wiki.services.openoffice.org/wiki/Optimization_Solver OpenOffice.org's Solver]
* [http://openopt.org OpenOpt] (BSD) a general purpose optimization framework written in Python and NumPy, capable of automatic differentiation.
* [http://code.google.com/p/pulp-or/ PuLP] (MIT license) a Python interface for expressing and solving [[LP]] problems.
* [http://rima.incremental.co.nz/ RIMA] (MIT license) a Lua interface for expressing and solving [[LP]] and [[MILP]] problems using CBC, CLP and lpsolve.

'''Unknown:'''

* [http://coool.mines.edu/ COOOL]

Another free list: [http://software.sandia.gov/Acro/html/Main/AcroPackages.html]

There are some more listed in the [ftp://rtfm.mit.edu/pub/usenet/sci.answers/nonlinear-programming-faq nonlinear-programming-faq].

== Free for non-commercial use ==

Trust region

* [http://www.numerical.rl.ac.uk/lancelot/blurb.html LANCELOT] (no redistribution or resale) Trust region method, adapt for bound constraints

Active set

* [http://www-unix.mcs.anl.gov/~more/tron/ TRON] (permission to copy and modify, but only to be used for 'internal research' ([http://plato.asu.edu/ftp/other_software/tron_f90.tar.gz download]) active set method that uses a combination of gradient projections and a preconditioned conjugate gradient method to minimize an objective function. TRON only provides for 'box' constraints and has no support for equality constraints, although it may be possible to add support for that by wrapping TRON around an NLA solver?

Sequential quadratic programming

* [http://plato.la.asu.edu/donlp2.html DONLP2] (dense; free for non-commercial purposes)

== Some proprietary alternatives ==

Generalised reduced gradient method:

* [[CONOPT]] (plus others in certain cases)
* [http://www.sbsi-sol-optimize.com/asp/sol_product_minos.htm MINOS] (uses GRG for linear constraints, else 'sparse SLC algorithm (a projected Lagrangian method, related to Robinson's method)' for nonlinear constraints. Used when gradient evaluation is cheap.
* MS Excel [http://support.microsoft.com/kb/q214115/ Solver].
* GRG2
* LSGRG2
* [http://www.pinterconsulting.com/ LGO] 'Lipschitz Global Optimizer'

Sequential quadratic programming:

* [http://www.sbsi-sol-optimize.com/asp/sol_products_snopt_desc.htm SNOPT] (sparse) Used when gradient evaluation is expensive. 'SNOPT employs a sparse SQP algorithm with limited-memory quasi-Newton approximations to the Hessian of Lagrangian. An augmented Lagrangian merit function promotes convergence from an arbitrary point.'
* [http://www.uni-bayreuth.de/departments/math/~kschittkowski/nlpqlp22.htm NLPQLP]
* [http://www.sbsi-sol-optimize.com/asp/sol_product_npsol.htm NPSOL]
* [http://www.sbsi-sol-optimize.com/asp/sol_lssol105description.htm LSSOL] (dense, 'two-phase (primal) quadratic programming')
* [http://www.princeton.edu/~rvdb/ LOQO] (free 30-day trial) 'LOQO is based on an infeasible, primal-dual, interior-point method applied to a sequence of quadratic approximations to the given problem'
* [http://www.mcs.anl.gov/~leyffer/solvers.html FilterSQP]

Active set method:

* [http://www.sbsi-sol-optimize.com/asp/sol_product_qpopt.htm QPOPT] (dense)

Other methods:

* [http://www.ziena.com/knitro.htm KNITRO] (three methods: interior point direct, interior point conjugate gradient, 'active set')
* [http://www.gams.com/dd/docs/solvers/pathnlp.pdf PATHNLP]. 'PATHNLP solves an NLP by internally constructing the Karush-Kuhn-Tucker (KKT) system of first-order optimality conditions associated with the NLP and solving this system using the PATH solver for complementarity problems'. Supposedly good for convex problems.
* [http://www.mosek.com/products.html MOSEK] (limited version available for download, or free student license) Interior point method plus simplex method.
* [http://www2.am.uni-erlangen.de/~kocvara/pennon/ PENNON] 'penalty method', 'PBM method of Ben-Tal and Zibulevsky'

Global optimisation

* [http://www.andrew.cmu.edu/user/ns1b/baron/baron.html BARON]
* [http://www.ganso.com.au/index.php GANSO]

Methods not yet checked:

* IMSL and NAG software libraries
''More to come''

Mixed integer/nonlinear programs:

* [http://www.gams.com/solvers/solvers.htm#DICOPT DICOPT]: MINLP

See also [[Survey of sparse matrix software]]

[[Category:Development]]
[[Category:Miscellany]]

Survey of optimisation software

2015-08-11T09:09:29Z

Dimitris: /* Free Open Source Software options */

The following is a survey of optimisation software that was performed as a part of our effort to identify options for a [[Non-proprietary Optimisation]] solver for ASCEND. Feel free to add any that we've missed.

== List of Lists ==

* List of NLP solvers: http://www.ici.ro/camo/hnp.htm
* List of unconstrained optimisation solvers: http://www.ici.ro/camo/huo.htm
* There ''was'' a nice list at http://www.scicomp.uni-erlangen.de/SW/opt.html but the link seems to be broken at the moment.
* 'Decision tree' for optimization software http://plato.asu.edu/sub/nlores.html
* Description of different types of optimisation problems: http://coool.mines.edu/report/node3.html

== Free Open Source Software options ==

* [https://projects.coin-or.org/Ipopt IPOPT] (LGPL) 'Interior-Point Filter Line-Search Algorithm'. Possibly some problems with scaling of variables (according to RPS). can use a number of free and non-free matrix solvers; the free matrix solver in version 3.3.1 is MUMPS. See also [[IPOPT]] in this wiki.
* [http://trilinos.sandia.gov/packages/moocho/ MOOCHO] (GPL?) reduced sequential quadratic programming (SQP); allows the user to supply their own linear solver.
* [http://www.gnu.org/software/gsl/manual/html_node/Multidimensional-Minimization.html GSL 'multimin'] (GPL) several multidimensional dense-matrix unconstrained optimisation methods including conjugate gradient methods, quasi-newton methods, steepest descent and Nelder-Mead simplex method.
* [http://acts.nersc.gov/opt++/index.html OPT++] (free, includes ''optional'' wrapping of non-free NPSOL). Good but dense matrices only (RPS). Superceded by MOOCHO?
* [http://software.sandia.gov/appspack/version5.0/index.html APPSPACK] (GPL?) 'asynchronous parallel generating set search', derivative-free.
* [http://www.eng.buffalo.edu/Research/MODEL/mdo.test.orig/CONMIN/ CONMIN] ('free' but where from?) 'two-step limited memory quasi Newton like Conjugate Gradient method with Beale restarts'.
* [http://www.cs.sandia.gov/SGOPT/ SGOPT] (LGPL) Evolutionary and pattern-search algorithms
* [http://www.math.ufl.edu/~hager/ OPTPACK] (PD) 'a dual algorithm for constrained optimization'
* [http://www.netlib.org/minpack/ MINPACK] (BSD-like) unconstrained
* [http://www.coin-or.org/Bonmin/ BonMin] (CPL) Part of the COIN-OR suite; a solver for convect MINLP problems.
* [https://projects.coin-or.org/Couenne Couenne] (CPL) Part of the COIN-OR suite; a solver for non-convex MINLP problems.
* [http://www.ime.usp.br/~egbirgin/tango/ ALGENCAN] (GPL) Augmented Lagrangian plus an embedded smooth function box-constraint solver called 'GENCAN'
* [http://www.ime.usp.br/~egbirgin/tango/ SPG] (GPL) for smooth function with convex constraint
* [http://www.gerad.ca/~couturgi/NOMAD/ NOMAD] (GPL) Generalized Pattern Search (GPS) algorithms to solve nonlinear optimization problems
* [http://www-fp.mcs.anl.gov/otc/Tools/LBFGS-B/ LBFGS-B] (PD?) limited-memory quasi-Newton code
* [http://ab-initio.mit.edu/wiki/index.php/NLopt NLopt] (LGPL) wrapper for a few other FOSS codes, but also reportedly has some new implementations of certain algorithms
* [http://www.uni-graz.at/imawww/kuntsevich/solvopt/ SolvOpt] (PD) 'method of exact penalisation', based on N.Z. Shor r-algorithm
* [http://openopt.org/ralg ralg] (BSD) - an implementation of N.Z. Shor r-algorithm; nonlinear/nonsmooth constrained/unconstrained problems

'''Metaheuristics'''
* [http://dev.heuristiclab.com/ HeuristicLab] (GPL) a framework for heuristic and evolutionary algorithms developed by Heuristic and Evolutionary Algorithms Laboratory (HEAL)

'''Wrappers'''

* [http://www.coin-or.org/NLPAPI/index.html NLPAPI] (GPL?) a generalised wrapper for NLP solvers, including support for LANCELOT.
* [https://projects.coin-or.org/GAMSlinks/ GAMSlinks] (GPL?) a wrapper for [https://projects.coin-or.org/ COIN-OR] solvers that allows them to be called from GAMS. This is interesting as it shows how we could implement set up ASCEND so that it can use GAMS solvers, which adapting FOSS solvers that run under GAMS much easier to adapt for use with ASCEND.
* [http://www.netlib.org/ampl/solvers/lancelot/ AMPL/LANCELOT] a wrapper for running LANCELOT from AMPL. Again, this provides a way for seeing how solvers that have been adapted for use in AMPL might be also be connected to from ASCEND.
* [http://cuter.rl.ac.uk/cuter-www/interfaces.html CUTEr] (GPL-like license) is a wrapper for a wide range of optimisation solvers, and also a testing framework.
* [https://projects.coin-or.org/Osi OSI] (CPL?) wrapper for quite a wide range of LP solvers, from COIN-OR.
* [https://projects.coin-or.org/OS OS] (CPL?) Optimisation Services, a number of interface languages and APIs for communicating between problem 'servers' and solver 'clients', with support for a range of COIN-OR solvers and converters for GAMS/AMPL input files.
* [http://wiki.services.openoffice.org/wiki/Optimization_Solver OpenOffice.org's Solver]
* [http://openopt.org OpenOpt] (BSD) a general purpose optimization framework written in Python and NumPy, capable of automatic differentiation.
* [http://code.google.com/p/pulp-or/ PuLP] (MIT license) a Python interface for expressing and solving [[LP]] problems.
* [http://rima.incremental.co.nz/ RIMA] (MIT license) a Lua interface for expressing and solving [[LP]] and [[MILP]] problems using CBC, CLP and lpsolve.

'''Unknown:'''

* [http://coool.mines.edu/ COOOL]

Another free list: [http://software.sandia.gov/Acro/html/Main/AcroPackages.html]

There are some more listed in the [ftp://rtfm.mit.edu/pub/usenet/sci.answers/nonlinear-programming-faq nonlinear-programming-faq].

== Free for non-commercial use ==

Trust region

* [http://www.numerical.rl.ac.uk/lancelot/blurb.html LANCELOT] (no redistribution or resale) Trust region method, adapt for bound constraints

Active set

* [http://www-unix.mcs.anl.gov/~more/tron/ TRON] (permission to copy and modify, but only to be used for 'internal research' ([http://plato.asu.edu/ftp/other_software/tron_f90.tar.gz download]) active set method that uses a combination of gradient projections and a preconditioned conjugate gradient method to minimize an objective function. TRON only provides for 'box' constraints and has no support for equality constraints, although it may be possible to add support for that by wrapping TRON around an NLA solver?

Sequential quadratic programming

* [http://plato.la.asu.edu/donlp2.html DONLP2] (dense; free for non-commercial purposes)

== Some proprietary alternatives ==

Generalised reduced gradient method:

* [[CONOPT]] (plus others in certain cases)
* [http://www.sbsi-sol-optimize.com/asp/sol_product_minos.htm MINOS] (uses GRG for linear constraints, else 'sparse SLC algorithm (a projected Lagrangian method, related to Robinson's method)' for nonlinear constraints. Used when gradient evaluation is cheap.
* MS Excel [http://support.microsoft.com/kb/q214115/ Solver].
* GRG2
* LSGRG2
* [http://www.pinterconsulting.com/ LGO] 'Lipschitz Global Optimizer'

Sequential quadratic programming:

* [http://www.sbsi-sol-optimize.com/asp/sol_products_snopt_desc.htm SNOPT] (sparse) Used when gradient evaluation is expensive. 'SNOPT employs a sparse SQP algorithm with limited-memory quasi-Newton approximations to the Hessian of Lagrangian. An augmented Lagrangian merit function promotes convergence from an arbitrary point.'
* [http://www.uni-bayreuth.de/departments/math/~kschittkowski/nlpqlp22.htm NLPQLP]
* [http://www.sbsi-sol-optimize.com/asp/sol_product_npsol.htm NPSOL]
* [http://www.sbsi-sol-optimize.com/asp/sol_lssol105description.htm LSSOL] (dense, 'two-phase (primal) quadratic programming')
* [http://www.princeton.edu/~rvdb/ LOQO] (free 30-day trial) 'LOQO is based on an infeasible, primal-dual, interior-point method applied to a sequence of quadratic approximations to the given problem'
* [http://www.mcs.anl.gov/~leyffer/solvers.html FilterSQP]

Active set method:

* [http://www.sbsi-sol-optimize.com/asp/sol_product_qpopt.htm QPOPT] (dense)

Other methods:

* [http://www.ziena.com/knitro.htm KNITRO] (three methods: interior point direct, interior point conjugate gradient, 'active set')
* [http://www.gams.com/dd/docs/solvers/pathnlp.pdf PATHNLP]. 'PATHNLP solves an NLP by internally constructing the Karush-Kuhn-Tucker (KKT) system of first-order optimality conditions associated with the NLP and solving this system using the PATH solver for complementarity problems'. Supposedly good for convex problems.
* [http://www.mosek.com/products.html MOSEK] (limited version available for download, or free student license) Interior point method plus simplex method.
* [http://www2.am.uni-erlangen.de/~kocvara/pennon/ PENNON] 'penalty method', 'PBM method of Ben-Tal and Zibulevsky'

Global optimisation

* [http://www.andrew.cmu.edu/user/ns1b/baron/baron.html BARON]
* [http://www.ganso.com.au/index.php GANSO]

Methods not yet checked:

* IMSL and NAG software libraries
''More to come''

Mixed integer/nonlinear programs:

* [http://www.gams.com/solvers/solvers.htm#DICOPT DICOPT]: MINLP

See also [[Survey of sparse matrix software]]

[[Category:Development]]
[[Category:Miscellany]]