Groupe d’études et de recherche en analyse des décisions

G-2017-71

CCGO: Fast heuristic global optimization

et

Global optimization problems are very hard to solve, especially when the nonlinear constraints are highly nonconvex, which can result in a large number of disconnected feasible regions. Complete methods based on spatial branch and bound can find a global optimum point, but can also be slow. Multi-start methods can be used instead when shorter solution times are important. These methods explore the variable space to identify promising points from which to launch a local solver. We present the CCGO multi-start heuristic which uses a combination of various types of initial point scatter, constraint consensus to move points toward feasibility, clustering to identify disconnected feasible regions, and simple search to improve point clusters, before selecting local solver launch points. It targets highly nonconvex models. This heuristic performs very well in comparison to existing commercial complete and multi-start solvers.

, 24 pages