A metaheuristic methodology based on the limitation of the memory of interval branch and bound algorithms

A metaheuristic methodology based on the limitation of the memory of interval branch and bound algorithms

0.00 Avg rating0 Votes
Article ID: iaor20117993
Volume: 50
Issue: 4
Start Page Number: 629
End Page Number: 644
Publication Date: Aug 2011
Journal: Journal of Global Optimization
Authors: ,
Keywords: programming: branch and bound, heuristics
Abstract:

Branch and Bound Algorithms based on Interval Arithmetic permit to solve exactly continuous (as well as mixed) non‐linear and non‐convex global optimization problems. However, their intrinsic exponential time‐complexities do not make it possible to solve some quite large problems. The idea proposed in this paper is to limit the memory available during the computations of such a global optimization code in order to find some efficient feasible solutions. By this way, we introduce a metaheuristic frame to develop some new heuristic global optimization algorithms based on an exact code. We show in this paper, with a small assumption about the sorting by breadth first of elements in the data structure, that the time‐complexity of such metaheuristic algorithms becomes polynomial instead of exponential for the exact code. In order to validate our metaheuristic approach, some numerical experiments about constrained global optimization problems coming from the COCONUT library were solved using a heuristic which certifies an enclosure of the global minimum value. The objective is not to solve completely the problem or find a better solution, but it is to know what is the highest precision which can be guaranteed reliably with the available memory.

Reviews

Required fields are marked *. Your email address will not be published.