Using Branch Bound Concepts in Construction-Based Metaheuristics: Exploiting the Dual Problem Knowledge

摘要

In recent years it has been shown by means of practical applications that the incorporation of branch & bound concepts within construction-based metaheuristics can be very useful. In this paper, we attempt to give an explanation of why this type of hybridization works. First, we introduce the concepts of primal and dual problem knowledge, and we show that metaheuristics only exploit the primal problem knowledge. In contrast, hybrid metaheuristic that include branch & bound concepts exploit both the primal and the dual problem knowledge. After giving a survey of these techniques, we conclude the paper with an application example that concerns the longest common subsequence problem. Christian Blum acknowledges support from the Spanish CICYT project OPLINK (grant TIN-2005-08818-C04-01), and from the Ramón y Cajal program of the Spanish Ministry of Science and Technology of which he is a research fellow. Monaldo Mastrolilli acknowledges support from the Swiss National Science Foundation project 200021-104017/1, Power Aware Computing, and by the Swiss National Science Foundation project 200021-100539/1, Approximation Algorithms for Machine scheduling Through Theory and Experiments.