Epidemieverhinderung in Netzwerken mit Integer Programming

Begriffe wie Infektionsketten, Kontaktverfolgung und Superspreader sind durch COVID-19 allgegenwärtig. In diesem Projekt wird versucht die Verbreitung von Viren in Netzwerken durch geeignete mathematische Modelle zu verhindern. Das Projekt zielt darauf ab, bekannte Netzwerkeffekte zu berücksichtigen und mithilfe ganzzahliger (linearer) Programmierung konkrete und effiziente Lösungsvorschläge zu entwickeln. Vorangegangene Studien zur Pandemieausbreitung berücksichtigen oftmals die soziale Organisation in Netzwerken nicht. Damit wird die Realität nicht abgebildet, da unsere Kontakte nicht gleichmäßig verteilt sind. Freundeskreis, Arbeitskolleg*innen, Schulklassen Menschen sind in Netzwerken organisiert, und entlang dieser Netzwerke entwickeln sich die Pandemien. Somit hat die Struktur dieser Netze einen signifikanten Einfluss auf die Ausbreitung von Pandemien. Interessanterweise gibt es hier Paralellen zur Ausbreitung von Werbebotschaften von Internet- Influencern, die sich über deren soziale Netzwerke verbreiten. Die vorhanden Forschungsergebnisse in dieser Richtung dienen als einer der Starpunkte des Forschungsprojekts. Die entwickelten Lösungscodes stehen anderen Forschern danach zur Verfügung. Das konzeptionelle Design soll darüber hinaus dabei helfen, Akzeptanz und Vertrauen in derartige KI- Lösungen (explainable AI) zu fördern, da die genutzten Lösungsverfahren im Vergleich zu vielen anderen Verfahren die in vorherigen Studien genutzt wurden beweisbar optimale Lösungen liefern.

Begriffe wie Infektionsketten, Kontaktverfolgung und Superspreader sind durch COVID-19 allgegenwärtig. In diesem Projekt wurde untersucht, inwiefern bestimmte mathematische Modellierungstechniken (ganzzahlige lineare Programmierung) geeignet sind die Verbreitung von Viren in Netzwerken zu verhindern. Das Projekt zielte darauf ab, bekannte Netzwerkeffekte zu berücksichtigen und konkrete und effiziente Lösungsvorschläge zu entwickeln. Vorangegangene Studien zur Pandemieausbreitung berücksichtigen oftmals die soziale Organisation in Netzwerken nicht. Damit wird die Realität nicht abgebildet, da unsere Kontakte nicht gleichmäßig verteilt sind. Freundeskreis, Arbeitskolleg*innen, Schulklassen - Menschen sind in Netzwerken organisiert, und entlang dieser Netzwerke entwickeln sich die Pandemien. Somit hat die Struktur dieser Netze einen signifikanten Einfluss auf die Ausbreitung von Pandemien. Interessanterweise gibt es hier Paralellen zur Ausbreitung von Werbebotschaften von Internet-Influencern, die sich über deren soziale Netzwerke verbreiten. Die vorhanden Forschungsergebnisse in dieser Richtung dienten als einer der Starpunkte des Forschungsprojekts. Außerdem erlaubt die ganzzahlige lineare Programmierung, dass beweisbar optimale Lösungen für die modellierten Probleme gefunden werden können. Im Vergleich dazu wurden in bisherigen Studien oft heuristische Verfahren und Simulationen genutzt, die solche beweisbar optimalen Lösungen nicht liefern können. Die grundlegende Problemstellung die studiert wurde modelliert die Personen (oder auch Familien, Arbeitsstätten, Schulen, etc) als Knoten in einem Netzwerk, die durch Kanten verbunden sind, wenn zwischen zwei Knoten eine Viren-Übertragung möglich ist. Nachdem diese Übertragung natürlich immer auch vom Zufall abhängt und bei manchen Verbindungen eine höhere Wahrscheinlichkeit der Übertragung da ist (z.B. durch engere oder häufigere Kontakte) wurde ein sogenanntes stochastisches Diffusionsmodell verwendet, das diese Zufallseffekte bei der Ausbreitung abbilden kann. Basierend auf dieser Grundlage wurde zwei konkrete Optimierungsprobleme und dafür angepasste Lösungsalgorithmen entwickelt. In beiden Problemen geht es darum, dass ein bestimmtes Budget für Maßnahmen vorhanden ist (blocken von Knoten bzw Kanten, was Quarantäne, Schulschließungen etc entspricht), und das Ziel ist, die Maßnahmen so zu setzen, dass möglichst wenige Knoten infiziert werden. Die entwickelten exakten Verfahren ermöglichen die beweisbar optimale Lösung für Netzwerke mit über 80000 Knoten innerhalb von 10 Minuten Laufzeit auf einem Standard-PC. Diese Ergebnisse zeigen, dass die exakte Lösung solcher Problemstellungen für Netzwerkgrößen, mit denen Städte modelliert werden können, möglich ist. Außerdem wurden innerhalb des Projekts auch Techniken für nicht-exakte (heuristischen) Verfahren auf die Problemstellungen adaptiert und mitgetestet. Die computationalen Resultate zeigen, dass diese heuristischen Verfahren Lösungen finden, die oft der Optimallösung entsprechen oder zumindest sehr nahe sind. Damit haben wir mit diesem Projekt auch empirische Evidenz gefunden, dass Techniken für heuristische Verfahren gute Ergebnisse liefern, was wichtig für Entscheidungen in der Praxis ist, da heuristische Verfahren eine viel weitere Verbreitung haben, da sie einfacher zu entwickeln sind, und auch noch besser als exakte Verfahren skalieren, da heuristische Verfahren eben nicht die Optimalität der Lösung die sie produzieren beweisen müssen.