O'Reilly logo

Optimization Techniques for Solving Complex Problems by Juan Antonio Gomez, Coromoto Leon, Pedro Asasi, Christian Blum, Enrique Alba

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

images CHAPTER 23

Solving the KCT Problem: Large-Scale Neighborhood Search and Solution Merging

C. BLUM and M. J. BLESA

Universitat Politècnica de Catalunya, Spain

23.1 INTRODUCTION

In recent years, the development of hybrid metaheuristics for optimization has become very popular. A hybrid metaheuristic is obtained by combining a metaheuristic intelligently with other techniques for optimization: for example, with complete techniques such as branch and bound or dynamic programming. In general, hybrid metaheuristics can be classified as either collaborative combinations or integrative combinations. Collaborative combinations are based on the exchange of information between a metaheuristic and another optimization technique running sequentially (or in parallel). Integrative combinations utilize other optimization techniques as subordinate parts of a metaheuristic. In this chapter we present two integrative combinations for tackling the k-cardinality tree (KCT) problem. The hybridization techniques that we use are known as large-scale neighborhood search and solution merging. The two concepts are related. In large-scale neighborhood search, a complete technique is used to search the large neighborhood of a solution to find the best neighbor. Solution merging is known from the field of evolutionary algorithms, where the union of two (or more) solutions is explored by a complete algorithm to ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required