Title | The cluster problem revisited |

Publication Type | Journal Article |

Year of Publication | 2014 |

Authors | Wechsung A, Schaber SD, Barton PI |

Journal | Journal of Global Optimization |

Volume | 58 |

Pagination | 429-438 |

ISSN | 0925-5001 |

Keywords | Cluster problem, Convergence order, convex relaxations, global optimization |

Abstract | In continuous branch-and-bound algorithms, a very large number of boxes near global minima may be visited prior to termination. This so-called cluster problem (J Glob Optim 5(3):253–265, 1994) is revisited and a new analysis is presented. Previous results are confirmed, which state that at least second-order convergence of the relaxations is required to overcome the exponential dependence on the termination tolerance. Additionally, it is found that there exists a threshold on the convergence order pre-factor which can eliminate the cluster problem completely for second-order relaxations. This result indicates that, even among relaxations with second-order convergence, behavior in branch-and-bound algorithms may be fundamentally different depending on the pre-factor. A conservative estimate of the pre-factor is given for alphaBB relaxations. |

URL | http://dx.doi.org/10.1007/s10898-013-0059-9 |

DOI | 10.1007/s10898-013-0059-9 |

# The cluster problem revisited

Submitted by tansh@mit.edu on