Scatter Search and Local NLP Solvers: A Multistart Framework for Global Optimization
Top Cited Papers
- 1 August 2007
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in INFORMS Journal on Computing
- Vol. 19 (3), 328-340
- https://doi.org/10.1287/ijoc.1060.0175
Abstract
The algorithm described here, called OptQuest/NLP or OQNLP, is a heuristic designed to find global optima for pure and mixed integer nonlinear problems with many constraints and variables, where all problem functions are differentiable with respect to the continuous variables. It uses OptQuest, a commercial implementation of scatter search developed by OptTek Systems, Inc., to provide starting points for any gradient-based local solver for nonlinear programming (NLP) problems. This solver seeks a local solution from a subset of these points, holding discrete variables fixed. The procedure is motivated by our desire to combine the superior accuracy and feasibility-seeking behavior of gradient-based local NLP solvers with the global optimization abilities of OptQuest. Computational results include 155 smooth NLP and mixed integer nonlinear program (MINLP) problems due to Floudas et al. (1999), most with both linear and nonlinear constraints, coded in the GAMS modeling language. Some are quite large for global optimization, with over 100 variables and 100 constraints. Global solutions to almost all problems are found in a small number of local solver calls, often one or two.Keywords
This publication has 11 references indexed in Scilit:
- Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear ProgrammingPublished by Springer Science and Business Media LLC ,2002
- Random Linkage: a family of acceptance/rejection algorithms for global optimisationMathematical Programming, 1999
- Handbook of Test Problems in Local and Global OptimizationPublished by Springer Science and Business Media LLC ,1999
- Numerical OptimizationPublished by Springer Science and Business Media LLC ,1999
- A template for scatter search and path relinkingPublished by Springer Science and Business Media LLC ,1998
- CONOPT—A Large-Scale GRG CodeINFORMS Journal on Computing, 1994
- Solving Large Sparse Nonlinear Programs Using GRGINFORMS Journal on Computing, 1992
- Stochastic global optimization methods part I: Clustering methodsMathematical Programming, 1987
- Stochastic global optimization methods part II: Multi level methodsMathematical Programming, 1987
- A projected Lagrangian algorithm and its implementation for sparse nonlinear constraintsPublished by Springer Science and Business Media LLC ,1982