A programação linear inteira é uma eficiente ferramenta na modelagem e solução de um grande número de problemas. São eles provenientes das mais diversas áreas, tais como recolhimento de lixo, planejame nto de sistemas de telecomunicações, cortes em uma, duas ou três dimensões, etc. Os problemas de programação linear inteiro de grande porte são freqüentemente impossíveis de serem resolvidos diretamente através de softwares comerciais. Em tais casos a re laxação lagrangeana, combinada com a otimização por subgradientes é muitas vezes usada para achar cotas inferiores para o valor ótimo da função objetivo. Estas cotas podem ser usadas, por exemplo, no método de Branch-and- Bound [Salkin and Mathur. 89], ou apenas para medir a qualidade das soluções viáveis. Tais propriedades encontram-se atualmente incorporadas em softwares comerciais como [CPLEX3.0 97], [OSL1.2 90], conforme descrito em MINTO [Nemhauser et alii. 94]. Outras estratégias também são consideradas: obtenção de cotas superiores, uma maior eficiência nas rotinas sobre a geração de cortes além do uso do processamento paralelo, veja, por exemplo [Nemhauser. 94] para o primeiro e [Lee. 94] para o último.