Algorithm Engineering für einige komplexe PraxisproblemeExakte Verfahren, Heuristiken und hybride evolutionäre Algorithmen

This work deals with the design of exact algorithms and heuristics for complex optimization problems that origin from three practical applications and one classical combinatorial task. We obtain exact algorithms by modeling our problems in terms of mathematical optimization problems and applying suitable software tools to solve this models. Because of the complexity of our problems, exact algorithms cannot solve large instances within adequate time. Therefore, on the one hand, we derive efficient heuristics by adapting algorithms for similar mathematical problems in a suitable manner. On the other hand, evolutionary algorithms have shown to be successfully applicable to many hard mathematical problems. For that reason, we experimentally determine appropriate EA frameworks, hybridizing the evolutionary operators with our problem specific heuristics.Diese Arbeit befasst sich mit dem Entwurf von exakten und heuristischen Lösungsverfahren für schwere Optimierungsprobleme, die aus drei praktischen Anwendungen und einer klassischen kombinatorischen Fragestellung stammen. Exakte Verfahren bekommen wir durch die Modellierung als mathematische Optimierungsprobleme und die Anwendung geeigneter Software für deren Lösung. Da die Komplexität der behandelten Probleme das exakte Lösen großer Instanzen in adäquater Zeit verbietet, werden zum Einen effiziente Heuristiken durch geeignete Erweiterungen bekannter Verfahren für verwandte mathematische Probleme der vorliegenden Praxisaufgaben gewonnen. Zum Anderen haben sich evolutionäre Algorithmen sehr erfolgreich bei der Bewältigung vieler mathematisch schwerer Optimierungsprobleme gezeigt. Daher werden experimentell geeignete EA-Rahmenwerke für die gegebenen Problemstellungen ermittelt und mit den zuvor gewonnenen Heuristiken hybridisiert