Column generation

Column generation or delayed column generation is an efficient algorithm for solving large linear programs.

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

o problema a ser resolvido é dividido em dois problemas: o problema principal e o subproblema. O problema mestre é 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 objetiva 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 naturais.

o processo funciona da seguinte forma. O problema principal está resolvido-a partir desta solução, podemos obter preços duplos para cada uma das restrições do problema principal. Esta informação é então utilizada na função objetiva do subproblema. O problema está resolvido. Se o valor objectivo do subproblema for negativo, foi identificada uma variável com um custo reduzido negativo. Esta variável é então adicionada ao problema mestre, e o problema mestre é re-resolvido. A re-solução do 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 para o problema mestre é ideal.

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

este artigo relacionado com Matemática Aplicada é um stub. Você pode ajudar a Wikipedia expandindo-a.