Uma abordagem bastante empregada e bem sucedida para se resolver Problemas de Otimização Combinatória consiste em formular o problema como um Programa Linear Inteiro e empregar algum algoritmo para avaliação de seus limites duais. Este, por sua vez, é inserido em um algoritmo de enumeração inteligente do tipo Branch-and-bound. Para que algoritmos Branch-and-bound sejam capazes de resolver instâncias de dimensões de interesse prático em tempos de computação aceitáveis, é necessário que as formulações de Programação Inteira empregadas forneçam limites duais fortes, isto é, que as formulações empregadas forneçam uma boa aproximação da envoltória convexa das soluções viáveis do problema. O projeto de pesquisa trata desta temática. Apresentamos abordagens para a geração de formulações fortes para a resolução de diversos problemas de Otimização Combinatória. As abordagens propostas fazem uso de mecanismos específicos de geração de desigualdades válidas (que exploram propriedades específicas do problema) bem como de procedimentos gerais (que empregam argumentos não específicos). Estes últimos, embora assim como os demais, é claro, forneçam desigualdades específicas para cada problema, podem ser generalizados do ponto de vista algorítmico. Uma dos principais pontos de originalidade do projeto consiste em combinar um destes mecanismos não específicos, denominado Lift-and-Project, em esquemas de geração de Limites Duais baseados em Relaxação Lagrangeana. Pelo que conhecemos, isto nunca foi proposto na literatura. As vantagens de algoritmos que conciliam as duas abordagens são: generalidade e estabilidade numérica. As atividades planejadas para o desenvolvimento do projeto contemplam: orientação de alunos de mestrado e doutorado, visitas técnicas nacionais e internacionais, submissão e apresentação de trabalhos científicos em revistas e congressos nacionais relevantes na área de Otimização Combinatória.