Dr. Martin Tieves
Kontakt / Forschung / Veröffentlichungen / Konferenzen und Workshops / Lehre
Forschungsbereiche
- Robuste Optimierung
- Design von Telekommunikationsnetzwerken
Themenschwerpunke: Network Design with Compression und Virtual Network Embedding - Algorithmische Heransgehensweisen an das equitable Knotenfärbungsproblem
Projekte
Siehe auch (link)- Virtual Network Embedding (VINO)
Förderung: BMBF Programm Mathematik für Innovationen in Industrie und Dienstleistungen
Die Informations- und Kommunikationstechnologien sind die unverzichtbare Basis unserer modernen Informations- und Wissensgesellschaft. Neben der Gewährleistung von Dienstgüte, Zuverlässigkeit und Sicherheit stellen dabei heutzutage vor allem der Energieverbrauch der Netze und die sich ständig ändernden Verkehrsstöhme infolge der Mobilität der Nutzer beim Netzzugang und der dynamischen Bereitstellung von Informationen und Rechenleistung durch Diensteanbieter grosse und neuartige Herausforderungen an die Netzplanung dar. Techniken zur Virtualisierung und Flexibilisierung der Netze und Diensteplattformen versprechen hier zwar eine effizientere und flexiblere Ausnutzung verfügbarer Ressourcen, führen aber im Gegenzug auch zu erheblich mehr Konfigurationsaufwand in den Netzen.
Heutige Methoden zur lang- und mittelfristigen Netzplanung beruhen meist auf Verkehrsprognosen für eine oder mehrere sogenannte Hauptverkehrsstunden und optimieren die Netze bezüglich dieser deterministischen Verkehrsanforderungen. Darüuber hinausgehende Verkehrsschwankungen werden, wenn überhaupt, nur als Störung des Normalfalls verstanden und mittels robuster Optimierung behandelt, ohne dass die in künftigen Netzen gegebenen vielfältigen Möglichkeiten zur Adaption berücksichtigt werden. Ein Grund hierfür liegt in der Tatsache, dass die heutigen mathematischen Techniken auf Szenarien mit derartigen komplexen Adaptionsmechanismen nicht anwendbar sind.
Hier setzen die Vorhaben dieses Verbundes an. Gesamtziel des Verbundes ist die Entwicklung neuartiger und praxistauglicher mathematischer Verfahren zur Optimierung virtueller und flexibler Kommunikationsnetze mit einer hohen zeitlichen Dynamik. Konkret sind zum einen die Planung und dynamische Anpassung von Flexgrid optischen Transportnetzen (Flexgrid Optical Network Design, FOND) und zum anderen die Einbettung und dynamische Anpassung von virtuellen Netzen in ein- oder mehrschichtige physikalische Netzinfrastrukturen (Virtual Network Embedding Problem, VNE) Gegenstand des Verbundprojekts VINO. Dazu wird ein Verbund aus drei Arbeitsgruppen mit Schwerpunkten in verschiedenen Bereichen der algorithmischen diskreten Mathematik, einer mathematisch orientierten Arbeitsgruppe aus dem Bereich der Kommunikationsnetze sowie drei Praxispartnern eingerichtet. Die Arbeitsziele der Partner ergänzen sich dabei sowohl thematisch als auch methodisch. Die Praxispartner im Verbund sind Nokia Siemens Networks, Anbieter von Produkten und Dienstleistungen im Kommunikationsbereich, ADVA Optical Networking, Hersteller optischer Netzkomponenten, sowie die Deutsche Telekom.
Ergebnisse (Auszug):
Poster (DRCN 2015)
Publikationen
Data Uncertainty in Virtual Network Embedding: Robust Optimization Approaches, Stefano Coniglio, Arie M.C.A. Koster, Martin Tieves, Journal of Network and Systems Management 24 (2016), no. 3, 681-710 (link).
Virtual network embedding under uncertainty: Exact and heuristic approaches, Stefano Coniglio, Arie M.C.A. Koster, Martin Tieves, 11th International conference on the Design of Reliable Communication Networks (DRCN 2015), IEEE (2015), 1-8. (link). - Branch-and-Bound Algorithmen für das equitable Graphenfärbungsproblem (EqColor)
Förderung: DFG Excellence Initiative
Dem Projekt liegt das equitable Färbungsproblem (EFP) zugrunde. Hierbei handelt es sich um eine Variante des Graphenfärbungsproblems, bei dem die zu bestimmenden Farbklassen eine ähnliche Kardinaliät aufweisen sollen. Ein bekanntes Anwendungsbeispiel kommt aus dem Bereich des Scheduling, dort sollen (in Konflikt stehende) Arbeitsaufträge (der Graph)) möglichst ausgeglichen auf mehrere Maschinen (Farben) verteilt werden.
Fig.1 - Eine equitable Färbung
Aufbauend auf das Undergraduate Funds Projekt Implementierung eines neuen Branch and Bound Verfahrens für das equitabl Färbungsproblem (IBBVeF) sollen die dort erzielten Resultate vertieft und erweitert werden. In diesem Projekt entwickelte der Student Sven Förster für das EFP Problem einen Branch-and-Bound Algorithmus welcher in seiner jetzigen Form vielversprechende Resultate liefert. Im Rahmen dieses Projektes wurden interessante Perspektiven für weitere Forschung aufgezeigt Daher bietet es sich an die wissenschaftliche Arbeit in diesem Themenkomplex auszubauen. Hierzu soll die wissenschaftliche Theorie erweitert und deren Resultate in die bisher erstellte Software integriert werden. - UP BEAT - User-friendly Program for Better Effectiveness of Advertising Tools
Förderung: DFG Excellence Initiative
Online Werbung ist ein wichtiges Element im Marketing Sektor. Das Marktvolumen für Online Werbung betrug 22.7 Milliarden USD in 2009 (Silverman 2010) und es wird erwartet, dass es im Jahr 2013 37.2 Milliarden USD umfassen wird (IAB 2009). Für Europa sind die Prognosen ähnlich. Man würde daher erwarten, dass es Kontrollmechanismen gibt, die sicherstellen, dass dieses Geld nur für entsprechend effiziente Werbemaßnahmen aufgewendet wird.
Dies ist jedoch nicht der Fall. Obwohl in der Regel eine große Menge an Daten verfügbar ist (z.B. die Aufnahme eines jeden Klicks auf einer Website) nutzen Forscher und Anwender meist nur simple Regressionsmodelle um das Ergebnis Ihrer Marketing Maßnahmen abzuschätzen und zu optimieren. Dennoch gibt es Forschungsergebnisse, die eine bessere Zuweisung von Werbebudget ermöglichen würden. Aufgrund Ihrer komplexen Natur, werden sie jedoch nur selten in der Praxis eingesetzt.
Das Ziel dieses Projektes ist es, die Nutzerfreundlichkeit, die Berechnungsgeschwindigkeit und die Flexibilitat dieser Methoden zu verbessern. Insbesondere sollen dabei sowohl kurzfristige als auch langfristige Synergieeffekte von Werbemittel analysiert und eingebunden werden. - METASOLVER - Konkurrierende Lösungsalgorithmen für Optimierungsprobleme
Förderung: DFG Excellence Initiative
Gemischt ganzzahlige lineare Programmierung ist eine der erfolgreichsten Methoden der diskreten Optimierung in den letzten 50 Jahren. Der immense Fortschritt in diesem Gebiet ist einerseits durch schnellere Comupter, andererseits aber auch durch bessere Algorithmen zu Erklären. Dennoch ist die unterliegende Struktur der Lösungsalgorithmen gleich geblieben: Die Branch and Bound Methode unterteilt das Problem in immer kleinere Subprobleme, Informationen von diesen werden dann genutzt um das gesamte Problem zu lösen. Wichtige Neuerungen sind in dem Zusammenhang Schnittebenen (gültige Ungelichungen) sowie das dynamische Generieren von Spalten, die den Lösungsverlauf beschleunigen können.
Der Wettbewerb zwischen den verschiedenen Software Anbietern (Cplex, Gurobi, SCIP) stimmuliert diese Entwicklung, sodass fortlaufende Verbesserungen erzielt werden. Diese Entwicklung hat jedoch auch Nachteile. Forscher und Anwender nutzen besagte Software oft als Black-Box. Die Auswahl der am besten geeigneten Software Variante ist hierbei zeitaufwendig und kostenintensiv. Zusätzlich ist es nicht direkt möglich, Implementierungen von der einen auf die andere Software zu übertragen. Nutzer laufen hierbei in Gefahr die falsche Entscheidung zu treffen, oder aber z.B. nach Software Updates Ihre Entscheidung revidieren zu müssen.
In diesem Projekt soll daher eine Grundlage geschaffen werden, Problem Implementierungen zwischen den jeweiligen Solvern auszutauschen zu können. Zusätzlich wird angestrebt verschiedene Solver parallel zu nutzen und dabei Informationen (Primal- und Dualschranken) auszutauschen um Synergieeffekte (bzw. Stärken) der einzelnen Solver auszunutzen.
letzte Änderung: 06.01.2017 - 10:36
math2.rwth-aachen.de