Rosiane de Freitas
Institute of Computing – UFAM, Brazil
Palestra/Lecture: Colorings, polyhedral MILP, and modern network optimization problems
Rosiane de Freitas is a Brazilian computer scientist, Associate Professor at the Institute of Computing of the Federal University of Amazonas, Brazil. Leader of the CNPq research group on “Optimization, algorithms and computational complexity”, she coordinates projects in collaboration with research groups around the world, with an emphasis on combinatorial optimization, algorithms, game, graph and scheduling theory, and integer/constraint programming. Representative of Brazil at Latin American Center for Computer Studies – CLEI. Former Vice-President representing Latin America at the International Federation of Operational Research Societies, coordinating the Committee for Developing Countries, until 2021. R&D project leader with large high-tech industry. Active in competitive programming, being a member of the programming contests steering committee of the Brazilian Computer Society (SBC) with ICPC, and coach of Brazilian and world finalist teams. Active in HR training actions for basic education, women in STEM, and technological innovation. Rosiane writes playful texts in the form of short stories for the dissemination of computer science, programming, and STEAM content.
Resumo da Palestra:
In this talk, we deal with special graph colorings and polyhedral combinatorics for MILP formulations, to better solve channel assignment problems in artificial/real-world mobile wireless networks. We consider graph coloring problems involving distance constraints as weighted edges. Some more general graph coloring problems were proposed in the literature that constitutes models for real applications, such as channel assignment in mobile wireless networks. Hale (1980) proposed he generalized coloring problem (GCP) where, for each edge, the absolute difference between colors assigned to each vertex must not be in a given forbidden set, problem that was later named T-coloring. Also, the bandwidth coloring problem (BCP), is a special case of T-coloring where the absolute difference between colors assigned to each vertex must be greater than or equal to a certain value (Malaguti and Toth, 2010; Lai and Lu, 2013; Dias et al., 2017), and the coloring problem with restrictions of adjacent colors (COLRAC, GEOM), where there is a restriction graph for which adjacent colors in it cannot be assigned to adjacent vertices (Trick et al, 2002, Akihiro et al., 2002).
In our research, we proposed theoretical modeling based on distance geometry and defined a hierarchy of coloring problems that we called distance graph coloring problems (DeFreitas et al., 2019). Thus, the vertices of the graph are considered as embedded on the real line and the coloring is treated as an assignment of positive integers to the vertices, while the distances correspond to line segments, where the goal is to find a feasible intersection. We proposed mixed-integer and constraint programming formulations and showed feasibility and optimality conditions for some problems (Dias et al., 2021). We also propose implicit enumeration methods for some of the optimization problems based on branch-and-prune algorithms proposed for DGPs in the literature. A polyhedral combinatorics study was conducted to define a distance polytope and facet-inducing inequalities (Dias et al. 2018). We propose new variations of vertex coloring problems in graphs, involving a new theoretical model in distance geometry (DG) for vertex coloring problems with generalized adjacency constraints, promoting the correlation between graph theory and DG fields. We also give a characterization and formal proof of polynomial cases for special graph classes, since the general main problem is NP-complete. We have also been developing technologies for data collection, antenna location, network throughput, connectivity path assurance, navigation, and exploring modern digital telecommunication technologies, including 5G, in a technological innovation R&D project with a large multinational telecommunications company.