O problema da partição convexa mínima

• Processo: 17/12523-9
• Modalidade de apoio: Bolsas no Brasil - Mestrado
• Data de Início da vigência: 01 de outubro de 2017
• Data de Término da vigência: 30 de novembro de 2018
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Cid Carvalho de Souza
• Beneficiário: Allan Sapucaia Barboza
• Instituição Sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
• Assunto(s): Programação linear inteira Geometria computacional Otimização combinatória Combinatória poliédrica
• Palavra(s)-Chave do Pesquisador: Combinatória Poliédrica | Geometria Computacional | Otimização Combinatória | Partição Convexa Mínima | programação linear inteira | Otimização Combinatória

Resumo

Neste trabalho, estudaremos formulações de programação linear inteira e heurísticas para o Problema da Partição Convexa Mínima. Uma partição convexa com respeito a um conjunto P de pontos no plano é uma divisão planar cujos vértices são pontos de P e as arestas sã um subconjunto dos segmentos de reta com extremidades em P. As arestas da envoltória convexa CH(P) de P definem a face ilimitada e todas as faces internas são polígonos convexos. No Problema da Partição Convexa Mínima, deseja-se encontrar uma partição convexa com o menor número de faces.O objetivo da pesquisa é investigar esse problema através de um estudo poliédrico que leve a um algoritmo exato e do desenvolvimento de heurísticas, analisando estas alternativas experimentalmente sobre um benchmark que deverá ser colocado em domínio público. Além disso, pretendemos desenvolver uma interface gráfica para visualizar instâncias e avaliar as soluções geradas pelos algoritmos implementados. (AU)