24 mar 2025
10:00 Defesa de Mestrado Auditório do IC3
Tema
Algoritmo de Branch-and-Price para Coloração de Grafos
Aluno
Ieremies Vieira da Fonseca Romero
Orientador / Docente
Rafael Crivellari Saliba Schouery
Breve resumo
O problema de coloração de vértices, um tema central da teoria dos grafos, consiste em atribuir cores aos vértices de um grafo de modo que vértices adjacentes não compartilhem a mesma cor, minimizando o número de cores utilizadas.
Amplamente aplicado em escalonamento, alocação de recursos e otimização de redes, esse problema desempenha um papel crucial na modelagem e resolução eficiente de cenários reais.
Esta dissertação explora métodos para resolver o problema de coloração de vértices por meio de formulações existentes de Programação Linear Inteira (PLI) e do método branch-and-price.
Um algoritmo de branch-and-reduce é empregado pela primeira vez no problema de precificação correspondente, integrando regras de separação e redução para simplificar a complexidade das instâncias, mantendo a integridade da solução.
Testamos a hipótese de que enumerar um maior número de colunas a cada etapa da abordagem de geração de colunas pode resultar em um menor tempo de execução total.
Combinamos essa estratégia com um conjunto de heurísticas para encontrar soluções viáveis, permitindo interromper o processo de geração de colunas mais cedo.
Além disso, os limites gerados por estas abordagens são utilizados para realizar separações e reduções ainda mais eficientes no problema original.
Experimentos computacionais em conjuntos de dados de referência DIMACS e MATILDA validam os métodos propostos, demonstrando melhorias significativas em eficiência.
Banca examinadora
Titulares:
| Rafael Crivellari Saliba Schouery | IC/UNICAMP |
| Teobaldo Leite Bulhões Júnior | CI/UFPB |
| Flávio Keidi Miyazawa | IC/UNICAMP |
Suplentes:
| Santiago Valdés Ravelo | IC/UNICAMP |
| Phablo Fernando Soares Moura | KU Leuven-Bélgica |