Saturday, January 3, 2015

Stopping criteria for meta-heuristics

When running a really small non-convex MIQP problem with GAMS+Localsolver I see:

LocalSolver 5.0 (Win64, build 20141120)
Copyright (C) 2014 Innovation 24, Aix-Marseille University, CNRS.
All rights reserved (see Terms and Conditions for details).

Searching for equations that define variables... found 5
Instance:       20 Variables
                 9 Constraints
                82 Expressions
               132 Operands

    time |           iterations |         #infeas
      0s |                    0 |               4
    time |           iterations |       objective
      1s |               583495 | 2.66000000e+002
      2s |              1406684 | 2.66000000e+002
      3s |              2235323 | 2.66000000e+002
      4s |              3073170 | 2.66000000e+002
      . . . . lots of lines with the same objective
    998s |            677978972 | 2.66000000e+002
    999s |            678600000 | 2.66000000e+002
   1000s |            679218601 | 2.66000000e+002

Stopped due to time limit.
Feasible solution found.
Objective Value: 2.66000000e+002

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

7 comments:

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

    I 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?

    ReplyDelete
  2. how did you find the global optimum
    Using a global solver (baron, glomiqo)

    ReplyDelete
  3. Its an interesting problem when dealing with clients who wants to know for how long they should run the algorithm to get good solutions.
    When 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!

    ReplyDelete
  4. Thanks Erwin for the answer.

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

    ReplyDelete
  6. Here is the lp file: residual.lp.

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

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

    ReplyDelete