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).

Based on the output, you can only claim that it was at the optimal solution for 99.9% of the time (instead of 99.99%).

ReplyDeleteI would not trust a meta-heuristic without benchmarking it against an exact algorithm on small instances first. That should give a sense on the running time vs optimality.

If the QPs are not convex (for fixed values of the binary variables), how did you find the global optimum?

ReplyDeletehow did you find the global optimumUsing a global solver (baron, glomiqo)

Its an interesting problem when dealing with clients who wants to know for how long they should run the algorithm to get good solutions.

ReplyDeleteWhen they have problems of many different sizes and shapes it is not possible to give a fixed timelimit without being very pessimistic. Having one KPI they could use as a rule of thumb could be nice, i will definitely look into the articles you list to get some inspiration! Thanks

Happy new year!

Thanks Erwin for the answer.

ReplyDeleteHi Erwin, can you share the instance you used? I'd like to try CPLEX global QP solver on it.

ReplyDeleteHere is the lp file: residual.lp.

ReplyDeleteI see in the lp model that GAMS leaves some leftovers in the model after substituting out the objective variable zobj. The Cplex presolver should take care of that.

Indeed the Cplex global MIQP solver has no problem with the model at all (I know it is small).

Thank you for the file and the newer post. Interesting example!

ReplyDelete