Um método estabelecido para resolver programas bilineares do tipo P é aplicar um tipo de relaxamento convexo para limitar os termos bilineares usando os envelopes de McCormick. Na abordagem padrão, cada termo bilinear é substituído por uma nova variável , e um conjunto de quatro restrições de desigualdade linear é adicionado à formulação, duas representando os superestimadores e duas os subestimadores.
Neste caso, a região viável será dada por inequações da seguinte forma:
Aqui, a inequação define o envelope convexo de , comumente referido como Envelope de McCormick. Pode-se também observar que o envelope induzido pela inequação pode ser obtido a partir das seguintes quatro multiplicações válidas:
%%
Usar a formulação do envelope de McCormick relaxa um problema não convexo em um problema convexo, resultando em uma LP que fornece um limite superior se as únicas não linearidades forem bilineares. Ao tornar um problema de maximização convexo, a solução máxima encontrada será um máximo global para o problema relaxado. Esta solução é então um limite superior para o problema original . Um limite inferior pode ser obtido resolvendo o problema não convexo original usando os valores obtidos do problema relaxado e, em seguida, verificando a viabilidade. Os Envelopes de McCormick fornecem um envelope que retém a convexidade enquanto minimiza o tamanho da nova região viável. Isso permite que as soluções de limite inferior obtidas utilizando esses envelopes sejam mais próximas da verdadeira solução do que se outros relaxamentos convexos fossem utilizados. No entanto, esse limite inferior pode ser fraco dependendo dos limites dos termos bilineares.