Scatter search and local NLP solvers: a multistart framework for global optimization.

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.

Key words: global optimization; multistart heuristic; mixed integer nonlinear programming; scatter search; gradient methods

1. Introduction

This paper describes OQNLP, a multistart heuristic algorithm designed to find global optima of smooth constrained nonlinear programs (NLPs) and mixed integer nonlinear programs (MINLPs). It uses the OptQuest Callable Library (OCL) implementation of scatter search (Laguna and Marti 2002) to generate trial points, which are candidate starting points for a local NLP solver. These are filtered to provide a smaller subset from which the solver attempts to find a local optimum. Our GAMS implementation can use any GAMS NLP solver, and the stand-alone version uses the generalized reduced gradient NLP solver LSGRG2 (Smith and Lasdon 1992).

The most general problem this algorithm can solve has the form

minimize f (x, y), (1)

subject to the nonlinear constraints