Summary

In Chapter 2 of this book, we first presented a problem-specific heuristic for the knapsack problem (cf. Section 2.2) and compared its solution to the optimal one.We realized that the difference in solution quality is considerable, although the greedy approach seemed to be promising at first glance mainly due to its intuitive principle. Of course it is not legitimate to generalize this observation since in some cases problem-specific heuristics are even proven to provide the optimal solution. However, in most cases, and particularly in real-world scenarios, results of limited quality are quite common. As a consequence, searching for better solutions seems to be the most obvious approach instead of trying to generate one single solution as “clever” as possible. Performing such a search in an effective and efficient way is, however, far from trivial. We have seen that enumerative methods indeed yield provably optimal solutions but at high computational costs which restrict their applicability. On the other hand, we observed that directing the search towards the greatest improvement in solution quality is insufficient, as it is likely to get stuck in a dead-end (cf. Section 3.2). This fact underlines the need for more advanced heuristic search strategies, which are able to explore the solution space in an effective way. in order to find high-quality or even near-optimal solutions. By definition, a search heuristic does not claim to yield optimal solution as exact (enumerative) optimization methods do. They rather aim at finding high-quality or even near-optimal solutions. Clearly, efficiency considerations play an important role in this context, as in many application scenarios solutions have to be found within a strictly limited amount of time. Since the earliest beginnings of metaheuristics, the above requirements have been raised to a meta-level, meaning that the proposed strategies are generic enough to be applied to a whole variety of optimization problems.