08 out 2021
10:00 Defesa de Mestrado Integralmente a distância
Tema
Partição de Grafos Eulerianos em Circuitos
Aluno
Pedro Olímpio Nogueira de Oliveira Pinheiro
Orientador / Docente
Orientador: Zanoni Dias / Coorientador: Cid Carvalho de Souza
Breve resumo
Uma partição em circuitos de um grafo consiste em particionar o conjunto de arestas desse grafo em subconjuntos, de forma que cada subconjunto induza um circuito no grafo original. Todo grafo euleriano pode ser particionado em circuitos, porém, diversas partições de tamanhos diferentes podem ser viáveis. No problema da Máxima Partição em Circuitos, o objetivo é encontrar uma partição em circuitos de um grafo euleriano com a maior cardinalidade possível. Para esse problema, propomos heurísticas gulosas, heurísticas que resolvem o modelo de Programação Linear Inteira (PLI) proposto por Caprara, Panconesi e Rizzi, com apenas um subconjunto das variáveis e sem necessidade de geração de colunas, e algoritmos exatos que resolvem o mesmo modelo PLI com geração de colunas. Para o modelo PLI, foi necessário a criação de um algoritmo para resolver o problema de pricing. Criamos um benchmark de instâncias e executamos diversos experimentos para avaliar esses algoritmos. Verificamos que a heurística PLI obtém os melhores resultados, obtendo solução ótima em quase 70% das instâncias utilizadas. Também abordamos o problema da Máxima Partição em Circuitos Alternados, em que as arestas do grafo possuem uma cor, entre preta e cinza, e os circuitos devem ser alternados, ou seja, arestas seguidas devem ter cores diferentes. Para esse problema, propomos heurísticas gulosas, uma heurística baseada na meta-heurística Busca Tabu e algoritmos exatos com uso de PLI. Criamos outro benchmark de instâncias, executamos experimentos e comparamos os resultados obtidos com resultados de algoritmos encontrados na literatura. Executar o algoritmo exato usando os dados obtidos pelas heurísticas foi o método que mostrou melhores resultados, superando os algoritmos da literatura e obtendo o resultado ótimo em 96.4% das instâncias usadas. Além disso, usamos as soluções do problema da Máxima Partição em Circuitos Alternados para resolver problemas de Rearranjo de Genomas e os nossos métodos também apresentaram os melhores resultados.
Banca examinadora
Titulares:
| Zanoni Dias | IC/UNICAMP |
| Kelly Cristina Poldi | IMECC/UNICAMP |
| Rafael Crivellari Saliba Schouery | IC/UNICAMP |
Suplentes:
| Orlando Lee | IC/UNICAMP |
| Yuri Abitbol de Menezes Frota | IC/UFF |