Heurísticas para el problema de suma de coloreo de aristas con vértices adyacentes distinguibles

Abstract

El problema de suma de coloreo de aristas con vértices adyacentes distinguibles (AVDSECP) consiste en buscar una asignación de colores a las aristas de un grato con las siguientes restricciones: todo par de aristas adyacentes tienen distinto color y todo par de vértices adyacentes debe tener diferencia en el conjunto de colores asignados a sus aristas incidentes. El objetivo es minimizar la suma de los colores a asignar tal que se cumplan las restricciones. Este problema es un caso particular de una gran familia de problemas conocida bajo el nombre de etiquetado de gratos, que resultan una herramienta muy útil para modelar situaciones de la vida cotidiana. Dada la pertenencia del AVDSECP a la clase de problemas NP-Difícil, en este trabajo presentaremos diferentes enfoques heurísticos para resolverlo. Agrupamos a estas heurísticas en dos categorías: procedimientos rápidos y procedimientos lentos (ya que consumen una cantidad de tiempo considerable teniéndose en cuenta que no son procedimientos exactos). Según el contexto de aplicación serán útiles unas u otras. Dentro de los procedimientos rápidos incluimos una heurística golosa. Además estudiamos dos modelos de programación por restricciones, uno de ellos enmarcado dentro de los métodos rápidos y el otro dentro de los lentos. También dentro del grupo de los procedimientos lentos, expondremos una heurística basada en una formulación de programación lineal entera con cantidad de variables exponencial, a la cual le aplicamos un proceso de generación de columnas. Presentaremos experimentos computacionales para analizar la performance de las diferentes heurísticas, buscando identificar cuales son los criterios que brindan el mejor rendimiento en cada una. Finalmente, concluiremos con una comparación entre las diferentes propuestas.