Métodos para solução do problema de coloração de fluxo

Abstract

Consider a graph G with a certain demand of flow to be sent from some source vertices to a target vertex. We call feasible flow a transmission of flow through the vertices and edges of G that meets the demand. Each feasible flow defines a multigraph with the vertices and edges of G, but with the multiplicity of each edge being equal to the amount of flow passing through that edge in the feasible flow. A feasible solution of the flow coloring problem consists of a feasible flow and an assignment of colors to the edges of its respective multigraph such that any two adjacent edges receive different colors. The goal of the problem is to find a feasible solution whose edge coloring has the least number of distinct colors. In this work, we present an approximation algorithm for the flow coloring problem that always uses fewer than ʟ(5X'ϕ + 2)/4˩ colors, where X'ϕ is the optimal number of colors. The approximation ratio of that algorithm improves the previous best ratio, 3/2, given by an algorithm by Campêlo et al. (2012). For this purpose, we have defined a new problem, which is solved in a step of our algorithm, and we prove that it can be solved in polynomial time. We present two novel integer linear programming formulations for the flow coloring problem and directly adapt a third one, initially proposed for a closely related problem. We also present a theoretical study of that three formulations. We propose a column generation based heuristic that can be implemented with two of the formulations studied. We present computational experiments performed with the two versions of the heuristic which shows that both can obtain, efficiently, solutions very close to the optimum. Finally, we suggest an exact algorithm, based on the branch-and-cut method, that uses one of the studied formulations and two inequalities that we have proved to be valid for this formulation.