When running a really small non-convex MIQP problem with GAMS+Localsolver I see:
LocalSolver 5.0 (Win64, build 20141120)
Searching for equations that define variables... found 5
time | iterations | #infeas
Stopped due to time limit.
Obviously the default stopping condition (max time = 1000s) is not very good for this case: we are just sitting there for
99.99% 99.9% of the time already at the optimal solution doing nothing useful. (266 is indeed the global optimum). In general these heuristics have no idea how close they are to an optimal solution, and just rely on the user to provide these time or iteration limits. (MIP solvers have this very powerful bounding information where we can say at any moment in time what the gap is between the best solution found an the best solution possible).
Is there nothing better we can do? There is some research on probabilistic stopping rules for these kind of algorithms (i.e. stop as soon as we think the probability we will find a better solution is small):
- Ribeiro, Rosseti, Souza, “Effective probabilistic stopping rules for randomized metaheuristics: GRASP implementations”, Learning and Intelligent Optimization, Lecture Notes in Computer Science Volume 6683, 2011, pp 146-160
- Boender, Rinnooy Kan, "Bayesian stopping rules for multistart global optimization methods", Mathematical Programming, 37:59–80, 1987.
- Dorea, "Stopping rules for a random optimization method", SIAM Journal on Control and Optimization, 28:841–850, 1990.
- Hart, "Sequential Stopping Rules for Random Optimization Methods with Applications to Multistart Local Search", SIAM Journal on Optimization, 1998, Vol. 9, No. 1 : pp. 270-290
- Safe, Carballido, Ponzoni, Brignole, “On Stopping Criteria for Genetic Algorithms”, Advances in Artificial Intelligence – SBIA 2004, Lecture Notes in Computer Science, 405-413, 2004
I would guess such a thing could well be a better default stopping rule.
PS Look at these iteration numbers. Don’t care here about a million iterations more or less. (Of course that is the whole purpose of this algorithm: do as many evaluations as possible).