Full text
| |
| Author(s): |
Mauricio Jose de Oliveira Zambon
Total Authors: 1
|
| Document type: | Master's Dissertation |
| Press: | Campinas, SP. |
| Institution: | Universidade Estadual de Campinas (UNICAMP). Instituto de Computação |
| Defense date: | 2014-11-27 |
| Examining board members: |
Pedro Jussieu de Rezende;
Fábio Luiz Usberti;
Cristina Gomes Fernandes
|
| Advisor: | Cid Carvalho de Souza; Pedro Jussieu de Rezende |
| Abstract | |
In this dissertation, we present the first algorithmic approach and the first experimental results in the literature for solving the Discrete Chromatic Art Gallery Problem (DCAGP). This problem is geometric in nature and consists of a variation of the classic Art Gallery Problem. In the latter, we want to find a minimum cardinality guard set that is able to watch over a given gallery. On the other hand, in the DCAGP, the objective is to find a set of watchers that covers the gallery and admits a valid coloring with a minimum number of colors. A coloring is valid if two watchers that observe a same point are assigned different colors. To solve this problem we apply two approaches: an exact and a heuristic one. Firstly, we present a primal heuristic able to provide good quality upper bounds, and subsequently an integer programming model that yields exact solutions for the DCAGP. This method was able to solve all instances from an extensive set of galleries, represented by randomly generated simple polygons, of up to 2500 vertices, in less than one minute. On another set of instances, where the representation includes polygons with holes and fractal von Koch polygons, with up to 800 vertices, this method found proven optimal solutions for 80% of the instances in less than 30 minutes. In the context of these solutions, we discuss the use of lazy constraints and techniques for strengthening the model, besides a brief analysis of the hardness of the instances. Moreover, we report on results obtained through a Lagrangian relaxation, mainly as a means to obtain good upper bounds, as well as from a variation of the relax-and-fix technique. Lastly, we discuss a branch-and-price process for solving the DCAGP to exactness (AU) | |
| FAPESP's process: | 12/24993-6 - Exact Solutions for the Chromatic Art Gallery Problem |
| Grantee: | Mauricio Jose de Oliveira Zambon |
| Support Opportunities: | Scholarships in Brazil - Master |