An augmented filled function for global nonlinear integer optimization

Abstract

The problem of finding global minima of nonlinear discrete functions arises in many fields of practical matters. In recent years, methods based on discrete filled functions have become popular as ways of solving these sort of problems. However, they rely on the steepest descent method for local searches. Here, we present an approach that does not depend on a particular local optimization method, and a new discrete filled function with the useful property that a good continuous global optimization algorithm applied to it leads to an approximation of the solution of the nonlinear discrete problem (Theorem 4). Numerical results are given showing the efficiency of the new approach.

Appendix

See Appendix Tables 4, 5, 6, 7, 8.

Table 4 Additional test functions: names and expressions

Table 5 Test functions, global minima

Table 6 Comparison with the average number of original function evaluations in Woon and Rehbock (2010)

Table 7 Comparison between the minimum number of function evaluations in Woon and Rehbock (2010) and our results

Table 8 Results. FF is the number of the filled function employed. $f_g$ is the minimum reached, and $n_{fu}$ and $n_{fill}$ are the number of function evaluations and the number of filled function evaluations