Problemas de Otimização Combinatória surgem em diversos contextos: no planejamento de redes de transporte e logística, de telecomunicações e computadores, em planejamento da produção, dentre outras aplicações. A adoção de soluções subótimas para estes problemas acarreta expressivas perdas econômicas. Uma maneira de se evitar, ou pelo menos atenuar estas perdas, consiste na proposição de melhores formulações matemáticas para modelar (e consequentemente, algoritmos de solução que exploram suas especificidades) tais problemas. Com isto, é possível obter soluções bastante próximas da otimalidade em tempos de computação aceitáveis. Para que isto ocorra, é necessário compreender porquê certas formulações e algoritmos são melhores do que outros. Embora algumas recomendações gerais possam ser estabelecidas, as respostas a estas questões são normalmente específicas aos problemas estudados. Neste projeto de pesquisa pretendemos investigar novas formulações matemáticas e propor novos algoritmos poliedrais de solução exata ou mesmo aproximada de Problemas de Otimização Combinatória. Com esta pesquisa pretendemos redefinir as dimensões máximas capazes de serem resolvidas na otimalidade e proporcionar um melhor compreensão teórica dos problemas estudados.