Taxonomia

European Journal of Operational Research 199 (2009) 620–629

Contents lists available at ScienceDirect

European Journal of Operational Research
journal homepage: www.elsevier.com/locate/ejor

Hybridizing exact methods and metaheuristics: A taxonomy
L. Jourdan *, M. Basseur, E.-G. Talbi
LIFL/INRIA/CNRS, Bat M3, Cité Scientifique, 59655 Villeneuve d’Ascq, France

a r t i c l e

i n f oa b s t r a c t
The interest about hybrid optimization methods has grown for the last few years. Indeed, more and more papers about cooperation between heuristics and exact techniques are published. In this paper, we propose to extend an existing taxonomy for hybrid methods involving heuristic approaches in order to consider cooperative schemes between exact methods and metaheuristics. First,we propose some natural approaches for the different schemes of cooperation encountered, and we analyse, for each model, some examples taken from the literature. Then we recall and complement the proposed grammar and provide an annotated bibliography. Ó 2008 Elsevier B.V. All rights reserved.

Article history: Received 22 September 2006 Accepted 10 July 2007 Available online 13 April 2008Keywords: Taxonomy Combinatorial optimisation Metaheuristics Exact methods

1. Introduction NP-hard problems are difficult to solve and no polynomial time algorithm are known for solving them. Unfortunately, most combinatorial optimization problems, such as the Travelling Salesman, N-Queens, Bin Packing, 0/1 Knapsack, Graph Partitioning, are NPhard. Two approaches can be considered to solve this kindof problems depending on their size. For small instances, researchers usually use exact methods. Exact methods find the optimal solution and assess its optimality. There exist numerous exact methods such as the family of Branch and X (Branch and Bound algorithm [58], Branch and Cut algorithm [42], Branch and Price algorithm [12]), Linear Programming, Dynamic Programing, etc. A branch and Xalgorithm uses a divide and conquer strategy to partition the solution space into subproblems and then optimizes individually each subproblem. Exact methods are known to be time expensive, so they can not be applied to large NP-hard problems or difficult ones. When instances become too large for exact methods, heuristics and in particular metaheuristics are often used. There are two main categories ofmetaheuristics: single solution algorithms and population based algorithms. The first category gathers local search (LS) [54], greedy heuristic (GH) [70], simulated annealing (SA) [50], tabu search (TS) [40], Iterated Local Search (ILS) [56] etc. The second category, which is more and more studied, regroups evolutionary algorithms such as genetic algorithms [44], evolution strategies [74], geneticprogramming [52], and also ant colonies (AC) [31], scatter search (SS) [39], immune systems [48] etc. However, in
* Corresponding author. E-mail addresses: laetitia.jourdan@inria.fr (M. Basseur), talbi@lifl.fr (E.-G. Talbi).

general, metaheuristics are not able to solve the problems to optimality and some convergence problems can be encountered. During the last years, many works have been realizedon cooperative (or hybrid) optimization approaches. In many cases, best results are obtained with this kind of approaches, especially on real-life problems. At the beginning, cooperations were mainly realized between several metaheuristics. But nowadays, more and more cooperation schemes between metaheuristics and exact approaches are proposed. These strategies usually give good results becausethey are able to exploit simultaneously the advantages of both types of methods. For example, it may allow to give quality guarantees to the identified solutions. In this article, we propose to survey the different cooperation between these two types of method. The fact that more and more papers deal with this kind of approaches (see Fig. 1) clearly indicates that it is an important issue for the...