Die Forschungsschwerpunkte des Instituts liegen im Bereich der Diskreten Mathematik und ihrer Anwendungen, insbesondere zu nennen sind Kombinatorische Optimierung, Chip-Design und Tourenplanung.
Publikationen & Technical Reports →
Die Kombinatorische Optimierung hat in den letzten Jahrzehnten wegen ihrer immensen Anwendungsrelevanz zunehmend an Bedeutung gewonnen. Am Forschungsinstitut für Diskrete Mathematik spielt sie schon immer eine wesentliche Rolle. Ausdruck dessen sind zahlreiche wegweisende Arbeiten der hiesigen Wissenschaftler und Gäste zu den unterschiedlichsten Fragestellungen der Kombinatorischen Optimierung. Der Artikel [1] gibt eine kurze Einführung. Einen umfassenden Überblick gibt das hier entstandene Standardwerk "Combinatorial Optimization" [2], von dem bereits sechs englische Auflagen erschienen sind. Wir richten häufig diverse internationale wissenschaftliche Tagungen aus.
Das Chip-Design ist vielleicht das interessanteste und vielseitigste Anwendungsgebiet der Mathematik überhaupt. Ohne Methoden insbesondere der Diskreten Mathematik kann heute keiner der hochkomplexen Chips mehr entworfen werden. Viele dieser Methoden sind hier am Institut entwickelt worden. Unsere enge Kooperation mit der Industrie ermöglicht das Arbeiten an den aktuellsten Technologien und den komplexesten Chips. Unsere "BonnTools" [3], die unter anderem innovative Algorithmen für Placement, Routing, Timing-Optimierung und Layout auf Transistorebene beinhalten, werden weltweit eingesetzt. Der Artikel [4] gibt eine kurze Einführung in das Chip-Design. Einen umfassenderen Überblick gibt [5].
Tourenplanung (Vehicle Routing) ist ein weiteres Anwendungsgebiet, dem wir uns widmen. Vor rund zehn Jahren haben wir eine neue Kooperation über die Optimierung von Zustelldiensten begonnen. Neben dem theoretischen Studium von Approximationsalgorithmen für Rundreise- und Vehicle-Routing-Probleme (siehe z.B. [6]) entwickeln wir einen Algorithmus für Tourenplanung in der Praxis, unter Berücksichtigung von tageszeitabhängigen Fahrtzeiten, heterogenen Flotten, Zeitfenstern und vielen anderen Nebenbedingungen (siehe [7]).
Zu den genannten Hauptthemen kann als einführende Literatur empfohlen werden:
| [1] | J. Vygen: Combinatorial Optimization. Princeton Companion of Applied Mathematics, Princeton University Press 2015 [Download] |
| [2] | B. Korte, J. Vygen: Combinatorial Optimization: Theory and Algorithms. Springer, Berlin, Sixth Edition 2018. [Informationen] |
| [3] | B. Korte, D. Rautenbach, J. Vygen: BonnTools: Mathematical innovation for layout and timing closure of systems on a chip. Proceedings of the IEEE 95 (2007), 555-572 [Download] |
| [4] | S. Held, S. Hougardy, J. Vygen: Chip Design. Princeton Companion of Applied Mathematics, Princeton University Press 2015 [Download] |
| [5] | S. Held, B. Korte, D. Rautenbach, J. Vygen: Combinatorial optimization in VLSI design. In: Combinatorial Optimization: Methods and Applications (V. Chvátal, ed.), IOS Press, Amsterdam 2011, pp. 33-96 [Download] |
| [6] | V. Traub J. Vygen: Approximation algorithms for traveling salesman problems. Cambridge University Press 2025 [Informationen] |
| [7] | J. Blauth, S. Held, D. Müller, N. Schlomberg, V. Traub, T. Tröbst, J. Vygen: Vehicle routing with time-dependent travel times: theory, practice, and benchmarks. Discrete Optimization 53 (2024), 100848 [arXiv] |
Das Forschungsinstitut für Diskrete Mathematik unterhält zahlreiche internationale Kooperationen und Drittmittelprojekte. Besonders erwähnenswert sind:
- eine fast 40 Jahre bestehende Kooperation über "Kombinatorische Optimierung und Chip Design" mit der Firma IBM. Siehe die Pressemitteilung der Universität.
- eine fast 10 Jahre bestehende Kooperation zuerst mit der Deutschen Post DHL und nun mit Greenplan über "Kombinatorische Optimierung für Anwendungen in Zustelldiensten" Siehe die Pressemitteilung der Universität.
- die Beteiligung am Hausdorff Center for Mathematics (Exzellenzcluster) mit Leitung der Forschungsbereiche "Optimization in large and complex networks" (2006–2012), "Algorithms, combinatorics, and complexity" (2012–2018), "Combinatorial optimization, complexity, and chip design (2019–2025), und "Combinatorial optimization, complexity, and applications" (2026–2032). Siehe die Meldung zur Förderung des HCM.