ANÁLISE DE FORMULAÇÕES E MÉTODOS HEURÍSTICOS PARA O PROBLEMA DO SUBGRAFO ACÍCLICO MÁXIMO COM RESTRIÇÕES DE CONFLITOS

Autores

  • Felipe Albuquerque Brito da Silva
  • Ana Karolinna Maia de Oliveira
  • Manoel Bezerra Campelo Neto

Resumo

Um grafo direcionado pode possuir ciclos, os quais podem ser não desejáveis ou proibidos em algumas aplicações práticas. Nesses casos, uma questão natural é determinar a menor quantidade de arcos cuja remoção do digrafo original o torna acíclico. O problema do Subgrafo Acíclico Máximo (SAM) de um grafo direcionado G=(V,A) consiste em encontrar o conjunto máximo A' contido em A tal que o subgrafo G'=(V,A') seja acíclico, sendo caracterizado como um problema NP-Difícil. No trabalho foi estudado o problema SAM sob restrições disjuntivas negativas, ou seja, define-se adicionalmente um conjunto de conflitos que impedem que certos pares de arcos estejam em uma solução viável. Formalmente, dado um grafo direcionado G=(V,A) e um grafo de conflitos Gc=(A,E) não direcionado, no qual os vértices representam os arcos de G e as arestas, os conflitos entre os arcos, o problema do Subgrafo Acíclico Máximo com Restrições de Conflitos (SAMRC) deseja descobrir o conjunto máximo A' contido em A tal que o subgrafo G'=(V,A') seja acíclico e A' seja um conjunto independente em Gc. Avaliamos três formulações de programação inteira para o problema SAM e suas adaptações para SAMRC. Além disso, desenvolvemos uma heurística para SAMRC baseada em coloração própria e em algoritmos aproximativos para SAM. Para a resolução das formulações e implementação das heurísticas foi utilizada a linguagem C++ e o resolvedor CPLEX. As instâncias de teste compreendem digrafos gerados aleatoriamente, com diferentes densidades e números de conflitos. A análise foi feita com respeito à obtenção de soluções ótimas e às melhores soluções com tempo limite de execução.

Publicado

2019-01-01

Edição

Seção

XXXVIII Encontro de Iniciação Científica