Pular para o conteúdo principal

Introdução

Lembre-se de que em um procedimento de Branch-and-Price, as restrições complicadoras foram removidas do RMP, deixando todo um poliedro definido fora dos cálculos. Como podemos verificar se existe alguma solução, no nosso caso, algum ponto extremo desse poliedro não considerado que possa melhorar nossa solução?

Suponha que

Considere que o poliedro removido dos cálculos originais é definido por:

Assim, aplicando Dantzig-Wolf, chegamos a:

Considerando o dual lagrangeano desse problema, obtemos:

Interessantemente, podemos notar que, para satisfazer , precisamos que

Em outras palavras, para termos uma solução viável para , que satisfaça as restrições duais, e considerando que a coluna resultante seja estritamente positiva, é suficiente resolvermos o seguinte problema auxiliar:

Assim, note que não foi necessário nesses cálculos, nem foi a solução original das variáveis primais do RMP.

Além disso, observe que, considerando a natureza positiva das variáveis, se o custo dado por não for positivo/negativo (dependendo do sentido da função objetivo), ele não satisfaz como uma solução viável para o Dual Lagrangeano.

Mais interessante ainda, o que estamos calculando aqui é a variável ''slack'' do dual lagrangeano. E, como sabemos, a partir das restrições de complementaridade, ou o slack é zero, ou a variável é zero (respeitando a relação primal/dual nisso). Então:

  • Se o sinal da solução do problema auxiliar estiver errado, não a aceitamos como uma nova coluna para o mestre, porque ela é inviável para o dual lagrangeano.
  • Se a solução do problema auxiliar tiver um valor de 0, também não a aceitamos como uma nova coluna, por causa da restrição de complementaridade.
  • Se a solução do problema auxiliar tiver o sinal correto, a aceitamos como uma nova coluna para o RMP.

Outra maneira de ver isso é colocando de volta '''' no objetivo do dual lagrangeano:

Como sabemos que o dual lagrangeano e o RMP devem dar a mesma solução ótima na convergência, quando o sinal está ''correto'', podemos ver claramente que, ao incluir essa nova variável encontrada pelo problema auxiliar, o problema ainda não convergiu.