Este trabalho explora a informaçao estrutural de relaçoes entre variáveis binárias em problemas de Programaçao Inteira por meio de grafos de conflitos. Tal estrutura possui um papel fundamental na construçao de métodos exatos e heurısticos de resoluçao. Nesse sentido, o presente trabalho propoe e desenvolve técnicas baseadas na análise de grafos de conflitos para obtençao de soluçoes factıveis e limites duais fortes para problemas de Programaçao Inteira. Foram desenvolvidas otimizaçoes nas técnicas de detecçao de conflitos, que permitiram a construçao rápida de grafos densos mediante a análise de restriçoes. A obtençao de limites duais fortes para programas inteiros é realizada por uma rotina desenvolvida para geraçao de desigualdades válidas. Essa rotina é responsável por gerar cortes de clique e ciclo ımpar e inseri-los na relaxaçao linear, reforçando os limites duais e acelerando a convergência para a soluçao ótima. Para obter soluçoes factıveis para programas binários foi desenvolvido um resolvedor heurıstico, que utiliza as relaçoes lógicas entre variáveis para construir uma soluçao inicial e melhorá-la por meio de uma busca local. A busca local executa uma cadeia de movimentos a cada iteraçao, que permite corrigir a infactibilidade de uma soluçao ou, até mesmo, saltar de uma soluçao factıvel para outra. Considerando a produçao de limites duais fortes, os resultados obtidos pela rotina de geraçao de desigualdades desenvolvida mostraram uma convergência mais rápida em relaçaoa rotina de separaçao de cortes do resolvedor COINOR Branch-and-Cut. Em relaçaoa obtençao de factibilidade, o resolvedor heurıstico foi apto a gerar soluçoes para um número significativo de problemas de Programaçao Inteira Binária, considerando tempos restritos de execuçao.