Geração de coluna - Column generation

Geração de coluna ou geração de coluna atrasada é um algoritmo eficiente para resolver grandes programas lineares .

A ideia geral é que muitos programas lineares são grandes demais para considerar todas as variáveis ​​explicitamente. A premissa é que a maioria das variáveis ​​será não básica e assumirá um valor zero na solução ótima. Por causa disso, apenas um subconjunto de variáveis ​​precisa ser considerado em teoria ao resolver o problema. A geração de colunas aproveita essa ideia para gerar apenas as variáveis ​​que têm potencial para melhorar a função objetivo - isto é, encontrar variáveis ​​com custo reduzido negativo (assumindo, sem perda de generalidade, que o problema é um problema de minimização).

O problema a ser resolvido está dividido em dois problemas: o problema principal e o subproblema. O problema principal é o problema original com apenas um subconjunto de variáveis ​​sendo considerado. O subproblema é um novo problema criado para identificar uma nova variável. A função objetivo do subproblema é o custo reduzido da nova variável em relação às variáveis ​​duais atuais, e as restrições exigem que a variável obedeça às restrições que ocorrem naturalmente.

O processo funciona da seguinte maneira. O problema mestre está resolvido - a partir dessa solução, podemos obter preços duais para cada uma das restrições do problema mestre. Essa informação é então utilizada na função objetivo do subproblema. O subproblema está resolvido. Se o valor objetivo do subproblema for negativo, uma variável com custo reduzido negativo foi identificada. Essa variável é então adicionada ao problema mestre e o problema mestre é resolvido novamente. Resolver o problema mestre irá gerar um novo conjunto de valores duais, e o processo é repetido até que nenhuma variável negativa de custo reduzido seja identificada. O subproblema retorna uma solução com custo reduzido não negativo, podemos concluir que a solução do problema mestre é ótima.

Em muitos casos, isso permite que grandes programas lineares que antes eram considerados intratáveis ​​sejam resolvidos. O exemplo clássico de um problema onde isso é usado com sucesso é o problema de corte de estoque . Uma técnica particular em programação linear que usa esse tipo de abordagem é o algoritmo de decomposição de Dantzig-Wolfe . Além disso, a geração de colunas foi aplicada a muitos problemas, como programação da tripulação , roteamento de veículos e o problema de p-mediana capacitada .