EMBEDDING METHODS INTO VNS TO SOLVE THE EDGE CROSSING MINIMIZATION PROBLEM

O problema de minimização de cruzamento (CMP, do inglês crossing minimization problem) é um problema de graph drawing (GD) para o qual foram dedicadas diversas pesquisas nos últimos trinta anos ou mais. No entanto, poucos estudos investigaram a aplicação de técnicas de aprendizado de máquina (AM) para resolver esse problema. Além disso, as estratégias existentes consideram aprendizado ponta-a-ponta e não utilizam-se de hibridizações com métodos de solução robustos, como as metaheurı́sticas. Em consonância com essa lacuna, este artigo apresenta uma metaheurı́stica variable neighborhood search que utiliza informações fornecidas por métodos de aprendizagem por representação em grafos. Experimentos computacionais indicam que dois dos três métodos investigados, DeepWalk e Node2vec, mostraram-se promissores para gerar uma solução inicial para o CMP, se comparados à estratégia aleatória.