Christian Blum

Combinatorial optimization is a branch of mathematical optimization concerned with problems where the solution space is finite but often too large for exhaustive search. Such problems arise in diverse domains, including logistics, bioinformatics, and scheduling. Two main approaches exist for tackling them: exact methods, which guarantee optimal solutions but scale poorly, and approximate methods, which trade optimality for efficiency. Within approximate methods lies the concept of metaheuristics, which are general frameworks that can be adapted to multiple combinatorial optimization problems. Notable examples include Ant Colony Optimization, Genetic Algorithms, and Tabu Search. Recently, the field of machine learning has attracted considerable attention, fueled by advances in computation and numerous breakthroughs. In particular, a rather novel and promising application is its integration into combinatorial optimization algorithms, particularly metaheuristics. In this context, learning can take place either offline, with models trained before the algorithm’s execution, or online, with models updated dynamically during the search. This thesis investigates both paradigms. On the offline side, it introduces an evolutionary framework for learning heuristic information to guide metaheuristics. The framework is employed in three settings: a genetic algorithm and a beam search applied to string-based optimization problems, and the Clarke and Wright heuristic for vehicle routing problems. On the online side, two novel variants of the hybrid metaheuristic Construct, Merge, Solve, and Adapt (CMSA) are proposed. Both integrate feedback from the exact solver used in the solve step of CMSA to improve solution construction, the first through a reinforcement learning–inspired mechanism and the second via deep learning, enabling richer adaptation during the search.