  The COVID-19 pandemic has been a recent example for the spread of a harmful
contagion in large populations. Moreover, the spread of harmful contagions is
not only restricted to an infectious disease, but is also relevant to computer
viruses and malware in computer networks. Furthermore, the spread of fake news
and propaganda in online social networks is also of major concern. In this
study, we introduce the measure-based spread minimization problem (MBSMP),
which can help policy makers in minimizing the spread of harmful contagions in
large networks. We develop exact solution methods based on
branch-and-Benders-cut algorithms that make use of the application of Benders
decomposition method to two different mixed-integer programming formulations of
the MBSMP: an arc-based formulation and a path-based formulation. We show that
for both formulations the Benders optimality cuts can be generated using a
combinatorial procedure rather than solving the dual subproblems using linear
programming. Additional improvements such as using scenario-dependent extended
seed sets, initial cuts, and a starting heuristic are also incorporated into
our branch-and-Benders-cut algorithms. We investigate the contribution of
various components of the solution algorithms to the performance on the basis
of computational results obtained on a set of instances derived from existing
ones in the literature.
