Neste projeto, propomos a investigação de cinco problemas de otimização combinatória que surgem no contexto de aplicações em Telecomunicações, Logística e em suas conexões com Teoria dos Jogos. São eles: O Problema das Árvores Geradoras Completamente Independentes, O Problema do Ciclo Elementar de Custo Mínimo de um Grafo, O Problema do Jogo em uma Árvore Geradora Mínima, O Problema do Jogo de Stackelberg em Árvores Geradoras de Custo Mínimo e o Problema da Árvore Geradora de Grau Completo. Para cada problema destacado, apresentamos formulações de programação inteira e algoritmos de resolução exata baseados nas técnicas de Decomposição de Dantzig-Wolfe, Decomposição de Benders, Relaxação Lagrangeana e Algoritmos de Planos de Corte. A equipe do projeto é formada por pesquisadores de diversas Universidades, bem como por alunos de doutorado do Programa de Pós Graduação em Ciência da Computação da UFMG.

Alunos envolvidos: Doutorado: (5) . Integrantes: Alexandre Salles da Cunha – Coordenador / Abilio Lucena – Integrante / Geraldo Robson Mateus – Integrante / Carlos Roberto Venâncio de Carvalho – Integrante / Fernanda S. H. Souza – Integrante / Luidi Simonetti – Integrante / Dilson Lucas Pereira – Integrante / SANTOS, FERNANDO AFONSO – Integrante / Vitor A.A. Souza – Integrante / Vinícius Wellington Coelho de Morais – Integrante / Rosklin Juliano Chagas – Integrante.