Advanced search
Start date

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

Grant number: 18/26434-0
Support Opportunities:Regular Research Grants
Duration: May 01, 2019 - 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


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)

Articles published in Agência FAPESP Newsletter about the research grant:
Articles published in other media outlets (0 total):
More itemsLess items

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)
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., . (14/12236-1, 18/26434-0, 18/14883-5)
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, . (18/14883-5, 18/26434-0, 14/12236-1)
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., . (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., . (14/12236-1, 19/22297-1, 18/26434-0)

Please report errors in scientific publications list using this form.