Problemas geométricos de decomposição

Author(s)

Allan Sapucaia Barboza

• Document type: Doctoral Thesis
• Press: Campinas, SP.
• Institution: Universidade Estadual de Campinas (UNICAMP). Instituto de Computação
• Defense date: 2022-08-22

Examining board members

Pedro Jussieu de Rezende; Alexandre Salles da Cunha; Yoshiko Wakabayashi; Rafael Crivellari Saliba Schouery; Lehilton Lelis Chaves Pedrosa

• Advisor: Cid Carvalho de Souza; Pedro Jussieu de Rezende

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 (AU)

• FAPESP's process: 18/14883-5 - Geometric decomposition problems
• Grantee: Allan Sapucaia Barboza
• Support Opportunities: Scholarships in Brazil - Doctorate (Direct)