Hotdog - a heuristic on the determination of optimum globally using the mathematical programming language AMPL

Abstract

An approach for robust, large-scale global optimization is developed, where robust refers to obtaining feasible local optimal solutions within constraints tolerances, and large-scale may imply nonconvex problems with hundreds to thousands of decision variables. A heuristic algorithm HOTDOG ("Heuristic On The Determination of Optimum Globally") is described for problems with a restricted number of local optima. A simpler version of the algorithm called MICIO ("MInimum Computation by Iterative Optimization") that uses the same local search procedure as HOTDOG, is also developed for use when the number of local optima is very large. Both algorithms are developed using the features and generic functions in the mathematical programming language AMPL, and both the HOTDOG and MICIO heuristics may therefore be invoked by a standard include-statement command in AMPL (corresponding to m-files in Matlab). To apply these heuristics certain AMPL modeling conventions have to be used. A modeling template describes these conventions with an example. Test results comparing HOTDOG/MICIO with other algorithms are also given.