Benders decomposition algorithms for minimizing the spread of harmful contagions in networks
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913328316547072 |
|---|---|
| author | Tanınmış, Kübra Aras, Necati Güney, Evren Sinnl, Markus |
| author_facet | Tanınmış, Kübra Aras, Necati Güney, Evren Sinnl, Markus |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2303_12402 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Benders decomposition algorithms for minimizing the spread of harmful contagions in networks Tanınmış, Kübra Aras, Necati Güney, Evren Sinnl, Markus Optimization and Control Discrete Mathematics 90C11, 90C57, 90C90 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. |
| title | Benders decomposition algorithms for minimizing the spread of harmful contagions in networks |
| topic | Optimization and Control Discrete Mathematics 90C11, 90C57, 90C90 |
| url | https://arxiv.org/abs/2303.12402 |