Algorithme de Branch and Bound à Mémoire Limitée

Depuis 2009 Une autre piste de recherche a été le développement d'une nouvelle approche métaheuristique pour la résolution de problèmes d'optimisation globale. L'idée est de limiter la mémoire disponible pendant l'exécution d'un algorithme de branch and bound par intervalles afin de trouver de manière plus efficace des solutions réalisables. Ainsi, au lieu d'améliorer une solution locale par des métaheuristiques, telles que le Tabou ou le VNS, cette approche débute avec une méthode globale qui se transforme en heuristique si toute la mémoire disponible est utilisée. De plus, une étude de la complexité montre qu'en fixant la taille de la mémoire disponible, la complexité de l'algorithme de Branch and Bound par intervalles devient polynomiale.