Minimizing Infection in a Topology using Mathematical Programming

  • Wesly C. Ataide UFSC
  • Pedro B. Castellucci UFSC
  • Álvaro J. P. Franco UFSC
  • Rafael de Santiago UFSC


Minimizing the spread of an infection is a key strategy for controlling an epidemic. In urban regions, the spread can be reduced by restricting movement between adjacent districts. We propose a non-linear integer programming model to minimize the number of infected people in a network. The network considers the relations between districts and the movement of people in a city. We develop methods to build and improve solutions. The model and the methods are evaluated on an instance based on real data. Finally, the results indicate how challenging the problem is from an optimization and numeric perspective.

Palavras-chave: non-linear programming, graphs, epidemiological models, epidemics


Bestuzheva, K., Besanc¸on, M., Chen, W.-K., Chmiela, A., Donkiewicz, T., van Doornmalen, J., Eifler, L., Gaul, O., Gamrath, G., Gleixner, A., Gottwald, L., Graczyk, C., Halbig, K., Hoen, A., Hojny, C., van der Hulst, R., Koch, T., Lübbecke, M., Maher, S. J., Matter, F., Mühmer, E., Müller, B., Pfetsch, M. E., Rehfeldt, D., Schlein, S., Schlösser, F., Serrano, F., Shinano, Y., Sofranac, B., Turner, M., Vigerske, S., Wegscheider, F., Wellner, P., Weninger, D., and Witzig, J. (2021). The SCIP Optimization Suite 8.0. Technical report, Optimization Online.

Carvalho, C., Costa, J., Sales, C. L., Lopes, R., Maia de Oliveira, A. K., and Nisse, N. (2020). On the characterization of networks with multiple arc-disjoint branching flows. Research report, UFC ; INRIA ; CNRS ; Université Côte d’Azur ; I3S ; LIRMM ; Université de Montpellier.

Chang, S., Pierson, E., Koh, P. W., Gerardin, J., Redbird, B., and Grusky, D. Leskovec, J. (2021). Mobility network models of covid-19 explain inequities and inform reopening. Nature, 589:82–87.

Dunning, I., Huchette, J., and Lubin, M. (2017). Jump: A modeling language for mathematical optimization. SIAM Review, 59(2):295–320.

Franco, Á . J. P. (2021). Epidemic model with restricted circulation and social distancing on some network topologies. In Cellular Automata, pages 261–264.

Liu, C., Wu, X., Niu, R., Wu, X., and Fan, R. (2020). A new sair model on complex networks for analysing the 2019 novel coronavirus (covid-19). Nonlinear Dynamics, 101(3):1777–1787.
Como Citar

Selecione um Formato
ATAIDE, Wesly C.; CASTELLUCCI, Pedro B.; FRANCO, Álvaro J. P.; SANTIAGO, Rafael de. Minimizing Infection in a Topology using Mathematical Programming. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 7. , 2022, Niterói. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2022 . p. 117-120. ISSN 2595-6116. DOI: