An Exact Algorithm for the Adjacent Vertex Distinguishing Sum Edge Coloring Problem

We define the \emph{adjacent vertex distinguishing sum edge coloring problem}. This problem consists in finding an assignment of colors to the edges of a graph with the following constraints: every pair of adjacent edges must have a different color, and every pair of adjacent vertices must not have the same set of colors assigned to the edges incident to each. The goal is to minimize the sum of the colors in an edge coloring that satisfies these constraints. This problem is a special case of a large family of problems known as \emph{graph labeling}, which is a widely used and very popular set of tools to build abstract models for problems that come up in everyday life.Some variants of \emph{graph labeling problems} have been successfully addressed with mixed integer linear programming (MIP) techniques based on a polyhedral characterization of the set of feasible solutions. We use this approach to develop a \emph{Branch and Cut} algorithm to solve the problem.%{\color{red} Furthermore, taking advantage of the analysis, we also propose an algorithm to solve the problem that minimizes the number of colors used for an \emph{adyacent vertex distinguishing edge coloring}.}%{\color{red} Additionally, we explored using heuristic techniques to solve the problem. These heuristics allow to obtain feasible coloring assignments for the problem but, in general, can not determine if they are optimal or even how far they are from the solution to the problem. We use three different approaches: a greedy algorithm, a constraint programming model and a column generation algorithm.}We propose two MIP models which are computationally evaluated to choose the most promising one and to continue with a polyhedral study. The polyhedral study aims to characterize valid inequalities so that they strengthen the formulation in hope of improving the algorithm's performance. These inequalities are added on demand as cutting planes with exact and heuristic separation algorithms. Moreover, we considered the use of an initial heuristic and a particular branching strategy.The results show that the algorithm developed allows us to solve instances that were unsolvable using general-purpose solvers. Our polyhedral study and the addition of cutting planes proved to be a crucial factor to solve the most challenging instances