The Critical Node Detection Problem applied to COVID-19 diffusion

The ongoing coronavirus disease, also known as COVID-19, has created a global health crisis with also deep social and economic impact. Individual testing has been shown as an an effective non-pharmaceutical intervention of contention of the virus, either on the absence of an effective vaccine or coexisting with one, as vaccines standalone are insufficient to prevent widespread transmission, disease, and morbidity. In a context where COVID tests are scarce, pricey and highly demanded it is key to define policies to optimize the allocation of them while promoting equality among people. In this thesis we will propose different strategies to either statically or dynamically allocate COVID tests among people to contain the spread of the virus while minimizing the number of tests. We conduct a literature review to learn from experience and design a mathematical model that mimics the diffusion behaviour of the COVID-19, the so-called SEPIA model. We propose and implement different strategies to find the most relevant people to test, also know as the Critical Node Detection Problem. Finally, a Reinforcement Learning algorithm, a branch of Machine Learning, is trained to be able to decide the number of tests to perform at each time step as well as how to allocate them depending on the number of reported COVID-19 cases seeking to minimize both the number of tests and the number of deaths related to COVID-19. Being able to model and simulate the diffusion of the COVID-19 pandemic plays a key role when designing non-pharmaceutical intervention, such as testing, to contain the spread of the virus. Contact tracing resulted as the most effective mitigation strategy, but a fair allocation of tests can contain the spread of the virus quickly, hence we combined it with buffer management techniques. Deciding how to act in response to the reported COVID cases optimizes the test allocation which is key in a test shortage context.