22 ago 2022
14:00 Defesa de Doutorado Sala 53 do IC (prédio 2)
Tema
Problemas Geométricos de Decomposição (em inglês: Geometric Decomposition Problems)
Aluno
Allan Sapucaia Barboza
Orientador / Docente
Orientador: Pedro Jussieu de Rezende / Coorientador: Cid Carvalho de Souza
Breve resumo
Problemas de decomposição, que incluem particionamento, cobertura e empacotamento, constituem um assunto central em Pesquisa Operacional. Estudamos variações geométricas desses problemas e apresentamos modelos de programação linear inteira (PLI) e heurísticas para eles. Lançamos também as bases para mais investigações com novos algoritmos e estruturas de dados, juntamente com benchmarks disponibilizados publicamente. Em primeiro lugar, estudamos a Problema da Partição Convexa Mínima de Conjuntos de Pontos, onde o objetivo é particionar a envoltória convexa de um conjunto de pontos P em um número mínimo de polígonos convexos vazios com vértices em P. Propomos um modelo PLI baseado em grafos e um baseado em arranjos. Para o segundo modelo, fornecemos uma implementação eficiente utilizando geração de colunas, juntamente com heurísticas, pré-processamento e regras de ramificação geométricas. Identificamos um pequeno subconjunto de faces do arranjo, ou seja, restrições suficientes para expressar o modelo, bem como uma estrutura de dados que permite consultas rápidas sobre somas de variáveis duais associadas a elas. Em segundo lugar, investigamos a Quadrangulação Convexa de Conjuntos de Pontos Bicromáticos com Inversões Mínimas. Nesse problema, dado um conjunto de pontos bicromático P, pede-se para encontrar o número mínimo de inversões de cores que permite que a envoltória convexa de P seja particionada em quadriláteros convexos vazios com vértices em P e arestas com extremidades de cores diferentes. Introduzimos um modelo PLI baseado em grafos e outro baseado em arranjos. O segundo modelo é uma nova abordagem que nos permite expressar atribuição de cores e particionamento do espaço como um modelo compacto de particionamento. Usamos esse modelo para derivar heurísticas análogas a abordagens de emparelhamento da literatura. Em terceiro lugar, estudamos o problema da Coesão, onde, dado um conjunto de pontos bicromático P, busca-se particionar P usando polígonos convexos maximizando a diferença mínima no número de pontos de cada cor cobertos por cada polígono. Descrevemos um modelo PLI com um número exponencial de variáveis que é eficientemente implementado usando geração de colunas. A combinação da relaxação deste modelo com uma heurística da literatura leva a um algoritmo de pré-processamento iterativo. Essa técnica foi capaz de resolver grande parte do nosso benchmark à otimalidade em tempo polinomial durante pré-processamento. Por fim, estudamos um problema de cobertura inspirado em redes sem fio, chamado de Cobertura Mínima 3-Colorível por Discos Unitários, onde, dado um conjunto de pontos P e um conjunto de discos unitários D, deseja-se encontrar uma cobertura mínima de P usando um subconjunto 3-colorível de D. Descrevemos um modelo PLI e mostramos como ele pode ser estendido e implementado iterativamente usando Decomposição de Benders Baseada em Lógica. Essa decomposição tem um problema mestre de cobertura e um subproblema de 3-coloração. Provamos que a solução da primeira iteração usa no máximo 18 vezes o menor número de cores dentre todas as coberturas de P por D. Também apresentamos algoritmos baseados em teoria de grafos e em geometria para obter cortes mais fortes, reduzindo significativamente o tempo de execução.
Banca examinadora
Titulares:
| Pedro Jussieu de Rezende | IC/UNICAMP |
| Alexandre Salles da Cunha | DCC/UFMG |
| Yoshiko Wakabayashi | IME/USP |
| Lehilton Lelis Chaves Pedrosa | IC/UNICAMP |
| Rafael Crivellari Saliba Schouery | IC/UNICAMP |
Suplentes:
| Cristina Gomes Fernandes | IME/USP |
| Cristiano Arbex Valle | DCC/UFMG |
| Flávio Keidi Miyazawa | IC/UNICAMP |
| Guilherme Pimentel Telles | IC/UNICAMP |