Solving nonconvex formulations of Euclidean steiner tree problems in N-space

• Processo: 14/50309-0
• Modalidade de apoio: Auxílio à Pesquisa - Regular
• Data de Início da vigência: 01 de setembro de 2014
• Data de Término da vigência: 31 de agosto de 2016
• Área do conhecimento: Engenharias - Engenharia de Produção - Pesquisa Operacional
• Acordo de Cooperação: University of Michigan
• Pesquisador responsável: Sandra Augusta Santos
• Beneficiário: Sandra Augusta Santos
• Pesquisador Responsável no exterior: Jon Lee
• Instituição Parceira no exterior: University of Michigan, Estados Unidos
• Instituição Sede: Instituto de Matemática, Estatística e Computação Científica (IMECC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
• Vinculado ao auxílio: 13/05475-7 - Métodos computacionais de otimização, AP.TEM
• Assunto(s): Problemas de otimização Problemas de n-corpos Problema da árvore de Steiner Heurística
• Palavra(s)-Chave do Pesquisador: Engenharia

Resumo

Este projeto foi motivado por experimentos numéricos recentes e preliminares com o modelo não convexo para o problema Euclidiano de Steiner. Visa superar duas dificuldades observadas nos experimentos, a saber: o mau desempenho dos limitantes inferiores obtidos via relaxações, e a não diferenciabilidade do modelo em pontos nos quais a solução é degenerada. Propomos investigar duas estratégias para superar tais dificuldades, quais sejam, um procedimento heurístico para gerar limitantes superiores para o valor da solução ótima, com o objetivo de validar cortes inteiros, bem como o uso de funções diferenciáveis para aproximar a norma Euclidiana. Nossa principal meta é desenvolver um algoritmo e uma implementação eficientes para problemas Euclidianos de Steiner para além dos bidimensionais, tendo em vista uma grande repercussão em técnicas que geram impacto nas diferentes áreas de problemas em otimização geométrica, como engenharia química e pesquisa operacional logística, entre outras. (AU)