Busca avançada
Ano de início
Entree

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

Processo: 19/11702-2
Linha de fomento:Bolsas no Brasil - Iniciação Científica
Vigência (Início): 01 de agosto de 2019
Vigência (Término): 31 de julho de 2020
Área do 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):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 noInstituto 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ássicoproblema 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.