No contexto de problemas na área das telecomunicações, propõem-se duas formulações em Programação Linear Inteira. Comparam-se estes modelos com uma formulação tradicional, analisando-se o espaço de soluções admissíveis das respectivas relaxações lineares (restrições de integralidade das variáveis são ignoradas). As características especiais das novas formulações permitem obter melhores limites inferiores para os valores das soluções óptimas inteiras dos problemas abordados e, consequentemente, essas soluções são obtidas com muito menor esforço computacional.