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

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.