Decomposição de Benders
- Proposto por
- Jacques F. Benders
- Ano
- 1962
- Tipo
- algorithm
- Família
- Optimization
Este texto é uma tradução automática e ainda não foi revisado. Ler o original em inglês
O que ele faz?
A Decomposição de Benders, introduzida por Jacques F. Benders em 1962, é um poderoso arcabouço algorítmico para resolver problemas de programação inteira mista (MIP) de larga escala.
Ela decompõe o problema em um problema mestre (controlando variáveis complicadoras) e subproblemas (lidando com as variáveis restantes), utilizando planos de corte gerados a partir de informações duais dos subproblemas para refinar iterativamente o problema mestre.
A intuição por trás do método
O método reconhece que certas variáveis (denominadas variáveis complicadoras) tornam o problema difícil de resolver diretamente, enquanto as variáveis restantes podem ser tratadas facilmente. Ao fixar as variáveis complicadoras e resolver o subproblema resultante para as variáveis restantes, o algoritmo obtém informações duais que geram planos de corte. Esses cortes fortalecem o problema mestre, que então seleciona melhores valores para as variáveis complicadoras. Este processo iterativo continua até a convergência. A percepção chave é que a decomposição transforma um problema difícil em muitos subproblemas mais fáceis mais um problema mestre menor.
História
Benders introduziu seu método de decomposição em 1962 para particionar problemas de programação inteira mista. Geoffrion generalizou a abordagem em 1972 para lidar com problemas não lineares, criando o arcabouço usado em aplicações modernas. O método ganhou proeminência com avanços em poder computacional e solvers. Desenvolvimentos recentes incluem cortes combinatórios de Benders, variantes de multi-corte e integração com algoritmos modernos de branch-and-cut, tornando-a uma técnica fundamental em otimização avançada.
Quando usar
Aplicar Decomposição de Benders a problemas de programação inteira mista de larga escala, particularmente aqueles com estrutura especial (escada, angular por blocos) explorável por decomposição. É especialmente eficaz para problemas onde métodos de solução direta são computacionalmente proibitivos. Usá-la para problemas de localização de instalações, planejamento de produção e projeto de redes. Para problemas pequenos ou aqueles sem estrutura especial, solvers MIP diretos podem ser mais eficientes.
Limitações e considerações
- Requer estrutura de problema adequada à decomposição; pode ser ineficiente em problemas totalmente gerais
- A geração de cortes pode criar muitas restrições, potencialmente retardando a resolução do problema mestre
- A convergência pode ser lenta, exigindo muitas iterações com tolerância rigorosa
- Complexidade de implementação maior que métodos de solução direta
- Questões de estabilidade numérica possíveis com coeficientes de corte
As condições da fonte não substituem a revisão científica independente nem a validação por um motor de análise.
Pontos fortes
- Resolve eficazmente programas inteiros mistos de larga escala que são intratáveis por métodos padrão
- Explora naturalmente a estrutura do problema com forma angular por blocos ou escada
- Fornece limites inferior e superior, permitindo garantias de qualidade antes da convergência
- A decomposição permite a resolução paralela de subproblemas independentes
- Benders Generalizado lida com subproblemas não lineares, ampliando a aplicabilidade
Aplicações
- Localização de instalações: determinar locais de armazéns e alocação de produtos para minimizar o custo total
- Planejamento de produção: agendar a produção em instalações com restrições de estoque e capacidade
- Roteamento de veículos: planejar rotas de entrega com decisões de composição de frota
- Projeto de redes: selecionar instalações, links e capacidades em redes de telecomunicações ou transporte
- Sistemas de energia: decisões de despacho econômico e compromisso de unidades com restrições de transmissão
- Otimização da cadeia de suprimentos: coordenar aquisição, produção e distribuição em redes
Como funciona
Como funciona
Configurar o problema mestre com apenas variáveis complicadoras e restrições de espaço reservado. Inicializar limites superior e inferior; limite inferior do mestre, limite superior de soluções factíveis.
Fixar variáveis complicadoras em seus valores atuais e resolver o subproblema para as variáveis restantes. Se infactível, gerar um corte de factibilidade; se factível, extrair informações duais e gerar um corte de otimalidade.
Adicionar cortes ao problema mestre refletindo insights do subproblema. Resolver novamente o problema mestre e repetir até que a lacuna entre os limites superior e inferior seja aceitável.
Erros comuns
- Seleção de escolhas ruins para variáveis complicadoras, resultando em subproblemas difíceis
- Falha na implementação de técnicas de estabilização (região de confiança, métodos de nível) para acelerar a convergência
- Geração de cortes fracos que não fortalecem suficientemente o problema mestre
- Ignorar pré-processamento e inícios quentes a partir de soluções factíveis
Perguntas frequentes
O que são variáveis complicadoras e como identificá-las?
Variáveis complicadoras são aquelas cujos valores, quando fixados, tornam o problema restante fácil de resolver. Elas são identificadas examinando a estrutura do problema: variáveis que aparecem em restrições que acoplam subproblemas independentes, ou variáveis discretas em problemas predominantemente contínuos, são candidatos comuns.
Qual a diferença entre cortes de factibilidade e cortes de otimalidade?
Cortes de factibilidade são gerados quando um subproblema é infactível, eliminando os valores infactíveis das variáveis complicadoras do mestre. Cortes de otimalidade incorporam informações duais de subproblemas factíveis para melhorar as estimativas do objetivo do mestre.
Como a Decomposição de Benders garante a convergência?
Cortes de factibilidade e otimalidade garantem que a relaxação do problema mestre forneça limites inferiores válidos. Limites superiores vêm de soluções factíveis do problema completo. Quando os limites convergem dentro da tolerância, a otimalidade é garantida. A convergência é finita para problemas inteiros limitados.
Quando a Decomposição de Benders é preferível a resolver o problema diretamente com um solver MIP?
A Decomposição de Benders é preferível quando o problema é grande, tem estrutura especial explorável por decomposição, ou solvers diretos excedem o tempo limite. Para problemas pequenos ou que carecem de estrutura, solvers MIP modernos são frequentemente mais rápidos e simples.
Métodos relacionados
Fontes
Benders, J. F. (1962). Partitioning procedures for solving mixed-variables programming problems. Numerische Mathematik, 4(1), 238-252.
Abrir referência DOICopiado.Geoffrion, A. M. (1972). Generalized Benders decomposition. Journal of Optimization Theory and Applications, 10(4), 237-260.
Abrir referência DOICopiado.