Colorações em grafos com restrições de distância: caracterizações, politopos e estratégias em programação matemática

Abstract

Graph coloring constitute a class of combinatorial optimization problems of great theoretical and practical relevance, with variations involving additional constraints to vertices or edges. One of its most important applications is in telecommunications, involving channel assignment in mobile wireless networks, where channels must be attributed to a set of devices while avoiding interferences. The Bandwidth Coloring Problem (BCP) addresses the general scenario of this application, where adjacent vertices receive different colors, which in turn must respect a separation that is imposed using weighted edges, generalizing the classic Vertex Coloring Problem (VCP). However, this model does not take into account all scenarios of channel assignment, creating the possibility of using other theoretical approaches to identify new models. In this thesis, we characterize new coloring problems with additional distance constraints, based on distance geometry and graph theory concepts, involving equalities and inequalities, and arbitrary and uniform values to represent distances, which can be applied to different characteristics of channel assignment, such as uni- and bidirectional communication. These theoretical models define a subclass of colorings with distances in graphs, for which we establish feasibility and computational complexity properties. We propose constraint programming formulations based on such problem definitions, using global constraints when vertices need more than one color. Also, we explore 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 assigned to vertices. Both new models have polynomial size, in contrast to existing ones that are pseudopolynomial. A polyhedral study is made where, for the new corresponding polytopes, we present their properties and some families of valid inequalities which define facets under certain conditions. To evaluate these new mathematical formulations, we developed exact computational strategies, including a cut-and-branch algorithm based on the orientation polytope and its valid inequalities. Experiments made using literature instances for BCP and channel assignment (where vertices may need one color or more colors) led to new better upper bounds for some instances and optimality proofs of heuristic solutions presented in the literature, and, principally, to new optimal solutions in other cases. Through these experiments, a comparative analysis between integer and constraint programming is presented, considering if vertices demand one or more colors. We observed that the new formulations, specially the orientation-based model and the cut-and-branch developed with it, were able to obtain optimal solutions in less time for many instances, establishing that the models have good potential to solve distance coloring problems. Our results provide important contributions for Graph Theory, Distance Geometry and Polyhedral Combinatorics for the graph coloring problems class.