Decomposição de Benders

Decomposição de Benders é uma técnica de programação matemática que permite resolver problemas de programação linear muito grandes, que possuam uma estrutura de blocos. Esta estrutura de blocos, muitas vezes, ocorre em aplicações tais como em programação estocástica, uma vez que a incerteza é geralmente representada através de cenários. A técnica é nomeada em homenagem a Jacques F. de Benders.

A decomposição de Benders usa uma estratégia de dividir para conquistar. Na decomposição de Benders as variáveis do problema são divididas em dois subconjuntos, de modo que um problema mestre é resolvido considerando apenas o primeiro conjunto de variáveis e os valores para o segundo conjunto de variáveis são determinados em um segundo estágio (problema escravo) usando os valores encontrados (fixados) para as variáveis do primeiro conjunto. Se o subproblema descobre que os valores fixados para o primeiro conjunto de variáveis é inviável, são gerados cortes de Benders que são adicionados ao problema mestre. O processo é então repetido até que não seja possível gerar mais cortes. Uma vez que a decomposição de Benders adiciona novas restrições à medida que progride em direção a uma solução, a abordagem é chamada de "geração de linhas". Em contraste, com a decomposição de Dantzig–Wolfe decomposição que usa geração de colunas.

Geralmente o primeiro conjunto de variáveis é dado pelas variáveis inteiras do problema e o segundo pelas variáveis contínuas. Dessa forma, o problema mestre constitui-se de um problema primal inteiro, já os problemas escravos são problemas duais lineares.

Aplicações

O problema de localização de facilidades está entre as aplicações de maior sucesso da decomposição de Benders. Castro et al. mostra que os subproblemas de Benders associados à formulação de programação matemática do problema de localização de facilidades podem ser separados em uma estruturada linear de blocos angulares de problemas de programação linear estruturados. Isto permitiu que fossem propostas soluções eficientes para grandes instâncias desses problemas, ao separar as variáveis do problema original em decisões binárias (correspondente ao posicionamento das facilidades) e decisões relacionadas ao transporte (correspondente ao fluxo de mercadorias).

Veja também

• FortSP solver usa a decomposição de Benders para a resolução de problemas de programação estocástica.

Referências

• Benders, J. F. (Set. 1962), "Particionamento de procedimentos para a solução mista-variáveis de problemas de programação", Numerische Mathematik 4(3): 238-252.
• Lasdon, Leon S. (2002), Optimization Theory for Large Systems reprint of the 1970 Macmillan ed. , Mineola, New York: Dover Publications, pp. xiii+523 .