CONICET | Buscador de Institutos y Recursos Humanos

El problema de suma de coloreo de aristas con v´ertices adyacentes distinguibles (AVDSECP) consiste en buscar una asignaci´on decolores a las aristas de un grafo con las siguientes restricciones: todopar de aristas adyacentes tienen distinto color y todo par de v´erticesadyacentes debe tener diferencia en el conjunto de colores asignados asus aristas incidentes. El objetivo es minimizar la suma de los colores aasignar tal que se cumplan las restricciones. Este problema es un casoparticular de una gran familia de problemas conocida bajo el nombre deetiquetado de grafos, que resultan una herramienta muy ´util 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´apidos y procedimientos lentos (ya que consumen una cantidad detiempo considerable teni´endose en cuenta que no son procedimientos exactos). Seg´un el contexto de aplicaci´on ser´an ´utiles unas u otras.Dentro de los procedimientos r´apidos incluimos una heur´ıstica golosa.Adem´as estudiamos dos modelos de programaci´on por restricciones, unode ellos enmarcado dentro de los m´etodos r´apidos y el otro dentro de loslentos. Tambi´en dentro del grupo de los procedimientos lentos, expondremos una heur´ıstica basada en una formulaci´on de programaci´on linealentera con cantidad de variables exponencial, a la cual le aplicamos unproceso de generaci´on de columnas.Presentaremos experimentos computacionales para analizar la performance de las diferentes heur´ısticas, buscando identificar cuales son loscriterios que brindan el mejor rendimiento en cada una. Finalmente, concluiremos con una comparaci´on entre las diferentes propuestas.