Uma relaxação MILP mais apertada pode ser construída ao particionar o domínio de uma das variáveis () do termo bilinear em (n) regiões disjuntas, com novas variáveis binárias sendo adicionadas à formulação para selecionar a partição ótima para .
A qualidade da relaxação é influenciada pela escolha das variáveis selecionadas para a partição. Em geral, pode existir um conjunto ótimo de variáveis que levaria à melhor relaxação, mas tal análise está além do escopo deste estudo. Na maioria dos problemas de engenharia, como no OMCOS, termos bilineares envolvem dois conjuntos diferentes de variáveis, então existem apenas algumas escolhas óbvias.
Sejam e , respectivamente, os limites inferior e superior da variável para a partição . Se o valor de pertencer a tal partição, então a variável binária e o respectivo envelope de McCormick se mantém. A Relaxação de McCormick por Partes pode ser formulada como um Programa Disjuntivo Generalizado, que é mais apertado devido ao uso dos parâmetros dependentes da partição e nas quatro restrições dentro da disjunção, em vez dos limites globais e . A região viável será definida por:
Visto que o GDP linear precisa ser reformulado em um MILP, uma alternativa consiste em aplicar a técnica do grande-M. No entanto, esta abordagem provou resultar em uma relaxação pobre, especialmente ao lidar com partições por partes. Por essa razão, a reformulação é realizada por meio de uma relaxação do invólucro convexo, conforme segue.
Observe que, se para algum , então e para todos . Além disso, , enquanto para todos .
Bivariate Piecewise McCormick
O domínio de ambas as variáveis que formam o termo bilinear é conhecido a priori, levando a uma relaxação que geralmente é mais apertada.
Na partição bivariada, ambas as variáveis são particionadas para obter uma relaxação mais apertada. A variável binária responsável por selecionar a partição ativa agora será . A variável é limitada por e , e a variável é limitada por e . A partição bivariada para a relaxação de McCormick por Partes é formulada como um Programa Disjuntivo Generalizado PR-BV-GDP.
Se a Relaxação de McCormick por Partes Bivariada for usada, a região viável será dada por:
Aplicar a reformulação do GDP linear em um MILP utilizando a técnica do invólucro convexo leva ao PR-BV-MILP. A variável corresponde ao valor que assume considerando o termo bilinear , a partição da variável e a partição da variável . As restrições abaixo garantem que será diferente de zero apenas se a partição bivariada for selecionada para o termo bilinear . Raciocínio semelhante se aplica para em relação à segunda variável do termo bilinear. Note que as variáveis assumem valores consistentes em todos os termos bilineares em que aparecem.
Aqui discutimos brevemente a reformulação do invólucro convexo do GDP na equação anterior. Considere um termo bilinear . Pela Eq. , exatamente uma partição é selecionada para a variável , e uma partição é selecionada para a variável . A Eq. garante que , enquanto as variáveis restantes para todos . Da mesma forma, a Eq. garante que , enquanto as variáveis restantes para todos . Agora pode-se ver que as Eqs. e garantem e , o que estabelece a consistência dos valores das variáveis e em todos os termos bilineares onde aparecem e suas respectivas partições.