Optimization Techniques for Solving Complex Problems

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