Rosiane Freitas, Federal University of Amazonas

Abstract

Graph coloring constitutes a class of combinatorial optimization problems of great theoretical and practical relevance with many applications, for which variations have been proposed in the literature, using different characteristics applied to vertices and edges. One of its most important applications is the channel assignment in mobile wireless networks, where channels must be attributed to devices while avoiding interferences, for which the Bandwidth Coloring Problem (BCP) has been proposed, where colors assigned to vertices must be separated according to weights imposed on edges. However, such a model does not take into account all scenarios of the channel assignment so other theoretical approaches can be used to identify new models. In this talk, we present new coloring problems based on distance geometry, generalizing the classic Vertex Coloring Problem (VCP) and BCP with adjacency constraints involving equalities and inequalities, which can be applied to different characteristics of the channel assignment, such as bidirectional communication. For the new models, we present feasibility and computational complexity properties. We propose constraint programming formulations based on such problem definitions, using global constraints for treating multi-coloring demands. Also, we explored integer programming models for BCP, improving an existing one and proposing two new others, based on orientations of the input graph and distances between colors. Both new models have polynomial size, in contrast to existing ones that are pseudopolynomial. For the new corresponding polytopes, we present their properties and valid inequalities which define facets under certain conditions. We also developed a cut-and-branch algorithm based on the orientation polytope and its valid inequalities. Our experiments show that this strategy has good potential for BCP, obtaining optimal solutions in less runtime when compared to the standard formulation for many literature instances.

Video