Algoritmos exatos e heurísticos para solução de problemas difíceis relacionados a geometria computacional

• Processo: 18/26434-0
• Modalidade de apoio: Auxílio à Pesquisa - Regular
• Vigência: 01 de maio de 2019 - 31 de outubro de 2021
• Área do conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Pedro Jussieu de Rezende
• Beneficiário: Pedro Jussieu de Rezende
• Instituição Sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
• Pesquisadores associados: Cid Carvalho de Souza
• Assunto(s): Geometria computacional Meta-heurística Otimização combinatória Programação linear inteira Algoritmos
• Palavra(s)-Chave do Pesquisador: Geometria Computacional | meta-heurísticas | Otimização Combinatória | programação linear inteira | Geometria Computacional e Otimização Combinatória

Resumo

O objetivo desta proposta é investigar soluções para diversos problemas combinatórios difíceis visando obter tanto heurísticas quanto métodos exatos que, na prática, sejam eficientes para resolver instâncias de grande porte. Os problemas tratados são relacionados com a área de geometria computacional e a maior parte deles apresenta características geométricas que, se bem exploradas, beneficiam o desenvolvimento de algoritmos. As várias técnicas utilizadas vêm principalmente de otimização combinatória (modelagem matemática, programação linear inteira, geração de colunas, algoritmos de planos de corte, relaxação lagrangiana), meta-heurísticas (como GRASP, busca tabu, entre outros), teoria de grafos e combinatória poliédrica. A pesquisa aqui proposta insere-se em teoria da computação, possui um forte componente de projeto e análise de algoritmos, mas também engloba diversos aspectos da área de experimentação computacional. (AU)

Publicações científicas

(4)

(Referências obtidas automaticamente do Web of Science e do SciELO, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores)

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)

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)

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)

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)