Geometric decomposition problems

Problemas de decomposição, que incluem particionamento, cobertura e empacotamento, constituem um assunto central em Pesquisa Operacional.Estudamos variações geométricas NP-difíceis desses problemas no plano 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 o Problema da Partição Convexa Mínima de Conjuntos de Pontos, cujo objetivo é particionar a envoltória convexa de um conjunto de pontos P em um número mínimo de polígonos convexos vazios (sem pontos de P em seu interior) com vértices em P .Propomos um modelo PLI baseado em grafos e outro 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 cujas arestas têm 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 coloração 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 em que, dado um conjunto de pontos bicromático P , busca-se particioná-lo 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 número exponencial de variáveis que é eficientemente implementado usando geração de colunas.A combinação da relaxação desse modelo com uma heurística da literatura produz um algoritmo iterativo de pré-processamento polinomial.Esse algoritmo foi capaz de resolver otimamente grande parte do nosso benchmark.Finalmente, estudamos um problema de cobertura inspirado em redes sem fio, chamado de Cobertura Mínima 3-Colorível por Discos Unitários.Neste problema, dado um conjunto de pontos P e um conjunto D de discos de mesmo raio, deseja-se encontrar uma cobertura mínima de P selecionando um subconjunto de D que pode ser colorido com até 3 cores.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 geométricos e baseados em resultados de teoria de grafos para obter cortes mais fortes, reduzindo significativamente o tempo de execução.

Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.