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

• Grant number: 18/26434-0
• Support Opportunities: Regular Research Grants
• Start date: May 01, 2019
• End date: October 31, 2021
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Pedro Jussieu de Rezende
• Grantee: Pedro Jussieu de Rezende
• Host Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil
• Associated researchers: Cid Carvalho de Souza

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)

Scientific publications

(4)

(References retrieved automatically from Web of Science and SciELO through information on FAPESP grants and their corresponding numbers as mentioned in the publications by the authors)

RAMOS, NATANAEL; DE REZENDE, PEDRO J.; DE SOUZA, CID C.. Optimal area polygonization problems: Exact solutions through geometric duality. Computers & Operations Research, v. 145, p. 10-pg., 2022-05-06. (18/26434-0, 14/12236-1)

SAPUCAIA, ALLAN; REZENDE, PEDRO J. DE; SOUZA, CID C. DE. Solving the minimum convex partition of point sets with integer programming. COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, v. 99, DEC 2021. (18/14883-5, 18/26434-0, 14/12236-1)

PEREIRA, FELIPE DE C.; DE REZENDE, PEDRO J.; DE SOUZA, CID C.; FERREIRA, CE; LEE, O; MIYAZAWA, FK. Effective Heuristics for the Perfect Awareness Problem. PROCEEDINGS OF THE XI LATIN AND AMERICAN ALGORITHMS, GRAPHS AND OPTIMIZATION SYMPOSIUM, v. 195, p. 10-pg., 2021-01-01. (14/12236-1, 19/22297-1, 18/26434-0)

SAPUCAIA, ALLAN; DE REZENDE, PEDRO J.; DE SOUZA, CID C.; GERVASI, O; MURGANTE, B; MISRA, S; GARAU, C; BLECIC, I; TANIAR, D; APDUHAN, BO; et al. Solving the Coarseness Problem by ILP Using Column Generation. COMPUTATIONAL SCIENCE AND ITS APPLICATIONS, ICCSA 2021, PT V, v. 12953, p. 16-pg., 2021-01-01. (14/12236-1, 18/26434-0, 18/14883-5)