Otimização combinatória: aspectos teóricos, formulação e aplicações

• Processo: 19/11702-2
• Modalidade de apoio: Bolsas no Brasil - Iniciação Científica
• Data de Início da vigência: 01 de agosto de 2019
• Data de Término da vigência: 31 de julho de 2020
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Carlos Eduardo Ferreira
• Beneficiário: Gabriel Morete de Azevedo
• Instituição Sede: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brasil
• Assunto(s): Otimização combinatória Teoria dos grafos Programação linear
• Palavra(s)-Chave do Pesquisador: Otimização Combinatória | otimização inteira | teoria dos grafos | Otimização Combinatória

Resumo

Este é um projeto de Iniciação Científica com duração de doze meses a ser desenvolvido no Instituto de Matemática e Estatística da USP. Nesse projeto, propomos o estudo de tópicos de otimização combinatória que incluem teoria de grafos, otimização inteira e algumas de suas aplicações principalmente com enfoque prático. Em particular, estamos interessados em formulações baseadas em programação linear: Dada uma matriz A mxn e vetores b, pertencente aos reais dimensão m e c, pertencente aos reais dimensão n devemos encontrar um vetor x, pertencente aos reais dimensão n, com todas as entradas não negativas que maximiza o produto cx sujeito a restrição Ax menor ou igual a b. Este tipo de formulação dispõe de muita versatilidade e há diversas ferramentas disponíveis como o Gurobi e o Cplex que são capazes de resolver problemas deste tipo de forma eficiente. Vários problemas de otimização combinatória têm aplicações interessantes. Um exemplo é o clássico problema do Caixeiro Viajante, que encontra aplicação no projeto de circuitos impressos. Outros problemas de interesse são o do caminho mínimo em um grafo, da árvore geradora de corte mínimo bem como o problema de alocação de recursos.