Menu

orcid.org/0000-0002-1736-3559

		Curriculum Vitae Download PDF
		DBLP entries
		Google Scholar Citations

Keynote Talk at Matheuristics 2016

In September 2016 I gave a keynote talk at Matheuristics 2016 which took place in Brussels, Belgium.

Titel: Combining Metaheuristics based on Solution Construction with Exact Techniques

Abstract: In this talk we deal with two different algorithmic approaches that combine metaheuristics with exact techniques. Both algorithms are based on the probabilistic construction of solutions: Beam-ACO is an algorithm that results from the combination of the metaheuristic ant colony optimization with beam search, which is a heuristic variant of branch and bound. On the other side, CMSA (Construct, Merge, Solve & Adapt) is a rather recent hybrid algorithm that is based on generating sub-instances to the tackled problem instance by means of probabilistic solution construction. These sub-instances are then solved to optimality by exact techniques. Both algorithms are introduced in the context of the multi-dimensional knapsack problem. Moreover, we show, in the context of the repetition-free longest common subsequence problem, that ideas from both algorithms can beneficially be combined into even more powerful algorithms. Finally, we start to explore the relation of CMSA with LNS (large neighborhood search). In particular, we show for which kind of problems CMSA can be a good alternative to LNS.

Download the slides