Pular para o conteúdo principal

Decomposição de Benders

A decomposição de Benders é uma técnica que resolve problemas de otimização de grande porte, dividindo-os em um problema mestre e um ou mais subproblemas. Ela é particularmente útil quando o problema apresenta restrições e variáveis de acoplamento que podem ser separadas em diferentes blocos.

Problema Original​

Considere um problema de otimização linear contínua da forma:

onde:

  • e são variáveis de decisão;
  • e são matrizes de restrições para ;
  • é a matriz de restrições para ;
  • e são vetores de constantes.

Este problema pode ser visto como composto de um problema mestre (variáveis ) e subproblemas (variáveis ), dado que as variáveis são acopladas com através da restrição .

Decomposição do Problema​

A decomposição de Benders separa e , resolvendo o problema em duas partes:

  1. Problema Mestre: As variáveis são mantidas no problema mestre.

  2. Subproblema: Dado um fixo, o subproblema para é resolvido para otimizar a função objetivo e garantir a factibilidade das restrições.

Problema Mestre Reformulado​

Primeiramente, reformulamos o problema original com a função objetivo do problema mestre:

onde:

A função representa o valor ótimo do subproblema dado um valor fixo de . No entanto, pode não ser facilmente calculada, então introduzimos uma abordagem iterativa baseada em planos de corte para resolver o problema mestre.

Subproblema Primal e Dual​

O subproblema para dado fixo pode ser escrito como:

Este subproblema é uma otimização linear que, como qualquer problema de programação linear, tem um problema dual associado. O problema dual é:

Aqui, são os multiplicadores duais associados às restrições . O valor de pode ser calculado a partir do valor ótimo do problema dual.

Duas Situações para o Subproblema​

O subproblema pode resultar em duas situações:

  1. Solução Ótima: O subproblema é factível, e existe um tal que . O valor de é finito e pode ser incorporado no problema mestre.

  2. Infactibilidade do Subproblema: O subproblema é infactível, o que significa que não há que satisfaça as restrições . Neste caso, o problema mestre deve incorporar cortes de viabilidade para evitar essa infactibilidade.

Condições de Infactibilidade​

Se o subproblema é infactível para um valor de , isso significa que a expressão para algum raio extremo do conjunto de soluções duais. Para evitar que isso aconteça, um corte de viabilidade é adicionado ao problema mestre:

onde é o conjunto de raios extremos.

Problema Mestre de Benders (PMB)​

Após resolver o subproblema e obter a função , o problema mestre é atualizado. O Problema Mestre de Benders pode ser escrito da seguinte forma:

Aqui:

  • é uma variável auxiliar que representa o valor de ;
  • e são os conjuntos de pontos extremos e raios extremos do problema dual.

Método de Planos de Corte​

Para resolver o Problema Mestre de Benders, o método de planos de corte é utilizado:

  1. Relaxação Inicial: O problema mestre inicial (PMB) contém apenas as restrições e possivelmente alguns cortes iniciais.

  2. Iteração: Em cada iteração , resolvemos o problema mestre atual (PMB) e obtemos uma solução .

  3. Subproblema: Com o obtido, resolvemos o subproblema correspondente. Se o subproblema for:

    • Factível: Calculamos e adicionamos um corte de otimalidade.
    • Infactível: Adicionamos um corte de viabilidade para eliminar essa região.

  4. Convergência: O processo continua até que o valor do problema mestre (limitante inferior) e o valor do subproblema (limitante superior) sejam suficientemente próximos.

Material didático retirado dos slides do prof. Pedro Munari da UFScar: https://www.dep.ufscar.br/munari/