Resumo: 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 Ver menos

Abstract: Decomposition problems, which include set-partition, set-cover and set-packing, constitute a core subject in Operations Research. We study NP-hard planar geometric variants of these problems and present integer linear programming (ILP) models and heuristics for them. We also lay the groundwork for further investigations with novel algorithms, data structures, and publicly available benchmarks. Firstly, we study the Minimum Convex Partition of Point Sets, where the goal is to partition the convex hull of a point set P into a minimum number of empty (with no points of P in their interior) convex polygons whose vertex set is P. We propose a graph-based and an arrangement-based ILP model for this problem. For the arrangement-based model, we provide an efficient column generation implementation, together with heuristics, preprocessing and geometry-based branching rules. We identify a small subset of faces of the arrangement, i.e., constraints, that suffice to express the model, as well as a data structure that enables fast queries on sums of dual variables associated to them. Secondly, we investigate the Convex Quadrangulation of Bichromatic Point Sets with Minimum Flips. In this problem, given a bichromatic point set P, one is asked to find the minimum number of color flips that allows the convex hull of P to be partitioned into empty convex quadrangles whose vertex set is P, and whose edges have endpoints of different colors. We introduce a graph-based and an arrangement-based ILP model for this problem. The second model is a novel approach that allows us to express coloring and space partitioning as a compact set-partition model. We use this model to derive heuristics analogue to matching approaches from the literature. Thirdly, we study the Coarseness problem where, given a bichromatic point set P, one seeks to partition P using convex polygons while maximizing the minimum difference between the number of points of each color covered by each polygon. We describe an ILP model with an exponential number of variables that is efficiently implemented using column generation. We combine the relaxation of this model with a heuristic from the literature leading to a polynomial-time iterative preprocessing algorithm. This algorithm solved to proven optimality a large portion of our benchmark. Lastly, we investigated a wireless network inspired set cover problem, called Minimum 3-Colorable Discrete Unit Disk Cover, where, given a point set P and a set D of disks of the same radius, one is asked to find a minimum cover for the points of P using a subset of D that can be colored with at most 3 colors. We describe an ILP model and show how it can be extended and implemented iteratively using Logic-based Benders Decomposition. This decomposition has a set-cover master problem and a 3-coloring subproblem. We prove that the solution of its first iteration uses at most 18 times the minimum number of colors from among all covers of P that use disks in D. We also present graph-theoretical and geometric algorithms to derive stronger cuts that significantly reduce the running time Ver menos