Geração de colunas para problemas de corte em duas fases / Column generation for two starge cutting stock problems

AUTOR(ES)

Aline Aparecida de Souza Leão

DATA DE PUBLICAÇÃO

2009

RESUMO

The Compartmentalized Knapsack Problem is an extension of the classical Knapsack Problem, where the ordered items are partitioned into classes, in such way that the knapsack must be divided into compartments, each one having limited capacity. In addition, the building of a compartment has a fixed cost and involves a loss of the overall capacity. The objective is to maximize the sum of the items utility value, minus the fixed costs of the compartments. This dissertation presents two solving methods. The first approach is a heuristic method, which is a combination of two heuristics from the literature. The second approach is a Column Generation method, that apart from it gives a new upper bound to the Compartmentalized Knapsack Problem, in the end of the method the master problem was solved with the variables defined as integer, that supplies a feasible solution. In both methods, the mathematical non linear model is decomposed into two linear models, one generates the compartments, and the other selects them to compose the knapsack. The results obtained with these two approaches were compared with an upper bound and they showed very efficient

ASSUNTO(S)

knapsack problems heurísticas heuristics column generation problemas da mochila geração de colunas cutting problems problemas de corte

Documentos Relacionados

• On stabilizing column generation for cutting stok problem
• O metodo de geração de colunas aplicado a problemas de otimização em grafos
• Algoritmos para problemas de corte e empacotamento
• Problemas de corte com sobras aproveitáveis e eliminação de simetrias
• Uma aplicação simulated annealing em problemas de corte de estoque