Summary

Günther Zäpfel (), Roland Braune () and Michael Bögl ()
Additional contact information
Günther Zäpfel: Universität Linz
Roland Braune: Universität Linz
Michael Bögl: Universität Linz

Chapter Chapter 11 in Metaheuristic Search Concepts, 2010, pp 291-299 from Springer

Abstract: Abstract 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.

Keywords: Solution Quality; Knapsack Problem; Vehicle Route Problem; Tabu List; Real Life Problem (search for similar items in EconPapers)
Date: 2010
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-642-11343-7_11

Ordering information: This item can be ordered from
http://www.springer.com/9783642113437

DOI: 10.1007/978-3-642-11343-7_11

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().