Skip to content
Voltar aos resultados

Geração de Colunas (Dantzig-Wolfe)

Proposto por
George B. Dantzig and Philip Wolfe
Ano
1960
Tipo
algorithm
Família
Optimization

Este texto é uma tradução automática e ainda não foi revisado. Ler o original em inglês

Tamanho da fonte

O que ele faz?

A Geração de Colunas, desenvolvida por George B. Dantzig e Philip Wolfe em 1960, é uma poderosa técnica de otimização para resolver problemas de programação linear em larga escala com estrutura especial. Também conhecida como Decomposição de Dantzig-Wolfe, ela decompõe o problema em um problema mestre (restrito a um subconjunto de variáveis/colunas) e um subproblema de precificação (identificando novas variáveis), melhorando iterativamente a solução pela introdução apenas de colunas relevantes.

A intuição por trás do método

O método reconhece que muitos problemas de otimização de grande porte possuem estrutura especial: numerosas variáveis, mas poucas restrições verdadeiramente importantes, ou subproblemas naturalmente decomponíveis. Em vez de resolver o problema completo com todas as variáveis possíveis, a geração de colunas mantém apenas um pequeno subconjunto de colunas (variáveis) promissoras. O problema de precificação, resolvido usando custos reduzidos e a estrutura do problema, identifica novas colunas que melhoram a solução mestra. Ao adicionar iterativamente as colunas mais promissoras, o algoritmo constrói uma solução eficientemente, evitando o fardo computacional de lidar com todas as colunas simultaneamente.

História

Dantzig e Wolfe introduziram o princípio de decomposição para programas lineares em 1960, estabelecendo a base teórica. Gilmore e Gomory (1961) aplicaram-no ao problema de corte de estoque, demonstrando poder prático. O método ganhou proeminência para problemas de roteamento de veículos e escalonamento nas décadas de 1980-90. A integração com branch-and-bound, criando algoritmos branch-and-price, expandiu a aplicabilidade para programação inteira. Aplicações modernas incluem escalonamento de tripulações de companhias aéreas, roteamento de navios e otimização logística em larga escala.

Quando usar

Aplique a geração de colunas ao resolver programas lineares em larga escala com estrutura especial, particularmente quando o número de variáveis é enorme, mas um pequeno subconjunto domina a solução ótima. É ideal para problemas de corte de estoque, roteamento de veículos, escalonamento de tripulações e empacotamento de caixas. Use-a quando a estrutura do problema permitir a solução eficiente do subproblema de precificação. Para problemas sem estrutura explorável ou de tamanho moderado, resolvedores de PL padrão são mais práticos.

Limitações e considerações

  • Requer estrutura de problema que permita a solução eficiente do subproblema de precificação
  • A convergência pode ser lenta, especialmente perto da otimalidade (efeito de cauda)
  • A solução do subproblema de precificação deve ser confiável e eficiente, ou os ganhos de eficiência são perdidos
  • Complexidade de implementação maior que métodos de PL padrão
  • Questões de estabilidade numérica com grandes valores duais e custos reduzidos

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 problemas de larga escala intratáveis por métodos padrão devido à explosão de colunas
  • Explora a estrutura do problema para gerar apenas colunas relevantes
  • Fornece limites na qualidade da solução durante a iteração
  • Naturalmente adequado para problemas com subestrutura especial (subproblemas idênticos, simetria)
  • Integrável com branch-and-bound para programas inteiros (branch-and-price)

Aplicações

  • Problema de corte de estoque: minimizar o desperdício ao cortar material em tamanhos exigidos
  • Roteamento de veículos: otimizar rotas para entrega e transporte com janelas de tempo e restrições de capacidade
  • Escalonamento de tripulações: atribuir membros da tripulação a voos ou turnos minimizando o custo total
  • Empacotamento de caixas: empacotar itens eficientemente em contêineres para minimizar o desperdício e o número de contêineres
  • Escalação de turnos: agendar trabalhadores em turnos respeitando a disponibilidade e as restrições de preferência
  • Planejamento de companhias aéreas: escalonamento de voos, atribuições de tripulação e coordenação de manutenção de aeronaves

Como funciona

Como funciona

1

Comece com um problema mestre restrito contendo apenas um subconjunto de colunas necessárias para uma solução factível inicial.

2

Resolva o dual do problema mestre restrito atual usando o tableau simplex. Identifique os custos reduzidos e configure o subproblema de precificação para encontrar variáveis com custo reduzido negativo (para minimização).

3

Resolva o subproblema de precificação usando sua estrutura especial. Se uma nova coluna com custo reduzido negativo for encontrada, adicione-a ao problema mestre e repita. Se nenhuma coluna melhoradora existir, a solução atual é ótima.

Erros comuns

  • Seleção de um algoritmo ineficiente para o subproblema de precificação, anulando os ganhos de eficiência da geração de colunas
  • Falha em reconhecer a estrutura do problema passível de decomposição, resultando em baixo desempenho
  • Detecção inadequada de convergência ou tolerância excessivamente rigorosa, desperdiçando iterações
  • Não implementação de técnicas de estabilização para lidar com o efeito de cauda

Perguntas frequentes

Qual é o problema de precificação na geração de colunas e como ele se relaciona com os custos reduzidos?

O problema de precificação identifica novas variáveis (colunas) com custo reduzido negativo que melhoram a solução mestra. Os valores de custo reduzido vêm do dual do problema mestre restrito e guiam a busca no subproblema de precificação.

Por que a geração de colunas é melhor do que resolver o problema completo com todas as colunas?

Em muitos problemas, o número de colunas potenciais é exponencial ou infinito, tornando impossível enumerá-las todas. A geração de colunas gera apenas as colunas necessárias sob demanda, reduzindo drasticamente o fardo computacional.

Qual é o efeito de cauda e como ele pode ser mitigado?

O efeito de cauda ocorre quando a geração de colunas faz progresso lento perto da otimalidade, gerando muitas colunas com melhoria mínima. Técnicas de estabilização (suavização dual, métodos de região de confiança, estratégias de corte) reduzem seu impacto.

Como o branch-and-price estende a geração de colunas para programação inteira?

Branch-and-price combina geração de colunas com branch-and-bound: em cada nó, a geração de colunas resolve a relaxação PL, e as decisões de ramificação restringem ainda mais o problema quando as soluções PL são fracionárias.

Métodos relacionados

Fontes

  1. Dantzig, G. B., & Wolfe, P. (1960). Decomposition principle for linear programs. Operations Research, 8(1), 101-111.

    Abrir referência DOI
    Copiado.
  2. Gilmore, P. C., & Gomory, R. E. (1961). A linear programming approach to the cutting-stock problem. Operations Research, 9(6), 849-859.

    Abrir referência DOI
    Copiado.