Exact and heuristic algorithms for solving difficult problems related to computational geometry

Abstract

The goal of this proposal is to investigate solutions to several difficult combinatorial problems with the intent of obtaining both heuristics and exact methods that are, in practice, efficient for solving large instances. The problems considered are related to the area of computational geometry and most of them present geometric characteristics that, if properly exploited, will benefit the development of algorithms. The various techniques used stem mainly from combinatorial optimization (mathematical modeling, integer linear programming, column generation, cutting plane algorithms, Lagrangian relaxation), metaheuristics (such as GRASP, tabu search, among others), graph theory and polyhedral combinatorics. The research in this proposal lies in the field of theory of computing, with a strong component from design and analysis of algorithms, while also encompassing many aspects of experimental computation. (AU)