In recent years appeared some examples of construction-based  metaheuristics that make use of branch & bound concepts during the solution construction. In the first part of this talk, 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 standard construction-based metaheuristics only exploit the primal problem knowledge. In contrast, hybrid techniques making use of branch & bound concepts exploit both the primal and the dual problem knowledge.

A prominent example is an algorithm called Beam-ACO, that is obtained by hybridizing ant colony optimziation with beam search.

In the second part of the talk, we will give a few application examples of Beam-ACO,  including the application to the longest common subsequence problem and simple assembly line balancing.

Alguma informação biográfica

Christian Blum is a research fellow at the Universitat Politécnica de Catalunya, Barcelona, under the programme Ramon y Cajal of the Spanish Ministry of Science and Technology.  He has obtained his PhD in Applied Sciences in 2004, on the subject "Theoretical and practical aspects of ant colony optimization" at the Université Libre de Bruxelles, Belgium, under the supervision of Prof. Marco Dorigo.

He has a very active participation in the meta-heuristics community, having received several prizes and being the organiser of important events in this field; in particular, he has been in charge of the Hybrid Metaheuristics conference since 2004.

He is associate editor of the journals Swarm Intelligence, Computers and Operations Research, and Innovative Computing and Applications.

Currently he has two book projects: one on swarm intelligence and another on hybrid metaheuristics, both to be published by Springer in 2008.