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 nonlinear 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. History: Accepted by Russell Bent, Area Editor for Network Optimization: Algorithms & Applications. Funding: The work of M. Cerulli was partially funded by project “SEcurity and RIghts in the CyberSpace” [Grant PE00000014] under the MUR National Recovery and Resilience Plan funded by the European Union - NextGenerationEU. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.0927 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2024.0927 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

Aircraft conflict resolution is one of the major tasks of computer-aided air traffic management and represents a challenging optimization problem. Many models and methods have been proposed to assist trajectory regulation to avoid conflicts. However, the question of testing the different mathematical optimization approaches against each other is still open. Standard benchmarks include unrealistic scenarios in which all the flights move toward a common point or completely random generated instances. There is a lack of a common set of test instances that allows comparison of the available methods under a variety of heterogeneous and representative scenarios. We present a flight deconfliction benchmark generator that allows the user to choose between (i) different predefined scenario inspired by existing benchmarks in the literature; (ii) pseudo-random traffic meeting certain congestion measurements; (iii) and randomly generated traffic. The proposed setting can account for different levels of difficulty in the deconfliction of the aircraft and allows to explore and compare the real limitations of optimization approaches for aircraft conflict resolution. History: Accepted by Ted Ralphs, area editor for Software Tools. Funding: This work was supported by the H2020 Marie Skłodowska-Curie Actions [Grant 764759 ITN “MINOA”]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.1265 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2021.0283 ) at ( http://dx.doi.org/10.5281/zenodo.7377734 ).