The previous pages of this website have described a number of incomplete and complete search methods, highlighting their strong points, as well as shortcomings. On one hand, incomplete search methods, including meta-heuristics, perform well when applied to unconstrained problems with a large number of feasible solutions, but cannot guarantee to find any sort of solution, especially if the problem is highly constrained. On the other hand, complete methods, such as CP , perform quite efficiently when applied to highly constrained problems, but do not fare so well with problems with a large number of feasible solutions. It seems quite logical that a combination of methods from these two categories could complement each other if put together.
There are several possible ways of integrating a meta-heuristic with a systematic search. In the first method, the systematic search and the meta-heuristic are sequentially applied. For example, the meta-heuristic (e.g. ACO or BOA ) can be run to produce some solutions which can be used by the systematic search method as heuristic information, or conversely the systematic search can be used to generate a partial solution which can then be completed by the meta-heuristic. The second method would involve the meta-heuristic using a systematic search, CP in particular, to efficiently explore the neighbourhood instead of using random sampling. The final method described talks about introducing concepts from one class of algorithms into the other, for example using a Tabu list with CP to manage the list of nodes that have not been explored yet. The remainder of this report will look at a number of hybrid techniques of incomplete and complete methods that have been suggested or investigated.