Preventing epidemics in networks using integer programming

Terms like infection chains, contact tracing and superspreaders are ubiquitous due to COVID-19. This project attempts to prevent the spread of viruses in networks using appropriate mathematical models. The project aims to account for known network effects and use integer (linear) programming to develop concrete and efficient solutions. Previous studies on pandemic spread often do not consider the social organization in networks. This does not reflect reality, as our contacts are not evenly distributed. Friends, work colleagues, school classes - people are organized in networks, and it is along these networks that pandemics develop. Thus, the structure of these networks has a significant impact on the spread of pandemics. Interestingly, there are parallels here to the spread of advertising messages from Internet influencers, which spread through their social networks. The existing research results in this direction serve as one of the starting points of the research project. The developed solution codes will be available to other researchers afterwards. The conceptual design is also intended to help promote acceptance and trust in such AI solutions ("explainable AI"), as the solution methods used provide provably optimal solutions compared to many other methods used in previous studies.

Terms such as infection chains, contact tracing and superspreaders are ubiquitous due to COVID-19. This project investigated the extent to which certain mathematical modeling techniques (integer linear programming) are suitable for preventing the spread of viruses in networks. The project aimed to take known network effects into account and develop concrete and efficient solutions. Previous studies on the spread of a pandemic often do not take social organization in networks into account. This does not reflect reality, as our contacts are not evenly distributed. Friends, work colleagues, school classes - people are organized in networks, and pandemics develop along these networks. The structure of these networks therefore has a significant influence on the spread of pandemics. Interestingly, there are parallels here with the spread of advertising messages from internet influencers that spread via their social networks. The existing research in this direction served as one of the starting points of our research. In addition, integer linear programming allows provably optimal solutions to be found for the modeled problems. In comparison, previous studies have often used heuristic methods and simulations that cannot provide such provably optimal solutions. The basic problem that was studied modeled people (or families, workplaces, etc.) as nodes in a network that are connected by edges if virus transmission is possible between two nodes. Since this transmission naturally always depends on chance and some connections have a higher probability of transmission (e.g. due to closer or more frequent contacts), a so-called stochastic diffusion model was used that can model these random effects. Based on this, two specific problems and solution algorithms were developed. In the problems, a certain budget is available for measures (blocking nodes or edges, which corresponds to quarantine, school closures, etc.), and the aim is to set the measures in such a way that as few nodes as possible are infected. Our exact methods enable the provably optimal solution for networks with over 80000 nodes within 10 minutes on a standard PC. These results show that the exact solution of such problems is possible for network sizes with which cities can be modeled. In addition, techniques for heuristic methods were also adapted and tested within the project. The results show that these heuristic methods find solutions that often correspond to the optimal solution or are at least very close to it. Thus, with this project we have also found empirical evidence that techniques for heuristic methods provide good results, which is important for decisions in practice, since heuristic methods have a much wider distribution, since they are easier to develop, and also scale better than exact methods, since heuristic methods do not have to prove the optimality of the solution they produce.