Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2408.16508 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915334234046464 |
|---|---|
| author | Archetti, Claudia Cerulli, Martina Sorgente, Carmine |
| author_facet | Archetti, Claudia Cerulli, Martina Sorgente, Carmine |
| contents | We tackle three optimization problems in which a colored graph, where each node is assigned a color, must be partitioned into colorful connected components. A component is defined as colorful if each color appears at most once. The problems differ in the objective function, which determines which partition is the best one. These problems have applications in community detection, cybersecurity, and bioinformatics. We present integer non-linear formulations, which are then linearized using standard techniques. To solve these formulations, we develop exact branch-and-cut algorithms, embedding various improving techniques, such as valid inequalities, bounds limiting the number of variables, and warm-start and preprocessing techniques. Extensive computational tests on benchmark instances demonstrate the effectiveness of the proposed procedures. The branch-and-cut algorithms can solve reasonably sized instances efficiently. To the best of our knowledge, we are the first to propose an exact algorithm for solving these problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_16508 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Branch-and-cut algorithms for colorful components problems Archetti, Claudia Cerulli, Martina Sorgente, Carmine Combinatorics Cryptography and Security Social and Information Networks We tackle three optimization problems in which a colored graph, where each node is assigned a color, must be partitioned into colorful connected components. A component is defined as colorful if each color appears at most once. The problems differ in the objective function, which determines which partition is the best one. These problems have applications in community detection, cybersecurity, and bioinformatics. We present integer non-linear formulations, which are then linearized using standard techniques. To solve these formulations, we develop exact branch-and-cut algorithms, embedding various improving techniques, such as valid inequalities, bounds limiting the number of variables, and warm-start and preprocessing techniques. Extensive computational tests on benchmark instances demonstrate the effectiveness of the proposed procedures. The branch-and-cut algorithms can solve reasonably sized instances efficiently. To the best of our knowledge, we are the first to propose an exact algorithm for solving these problems. |
| title | Branch-and-cut algorithms for colorful components problems |
| topic | Combinatorics Cryptography and Security Social and Information Networks |
| url | https://arxiv.org/abs/2408.16508 |