Publicação
An efficient dynamic programming algorithm for the Unbounded Knapsack Problem
| Resumo: | This report describes an algorithm for the Unbounded Knapsack Problem based on the algorithm EDUK (Efficient Dynamic Programming for the Unbounded Knapsack Problem). EDUK takes advantage of the problem properties of dominance and periodicity to speed up computation. This algorithm is compared with other implementations and it is tested both with randomly generated instances and with instances generated from a delayed column generation for the Cutting Stock Problem. This report also contains an analysis of unbounded knapsack instances. |
|---|---|
| Autores principais: | Moura, Leonardo Fernando dos Santos |
| Assunto: | Algoritmos Gramatica : Grafos Unbounded knapsack problem Cutting stock problem Column generation |
| Ano: | 2013 |
| País: | Brasil |
| Tipo de documento: | trabalho de fim de curso |
| Tipo de acesso: | acesso aberto |
| Instituição associada: | IBICT |
| Idioma: | inglês |
| Origem: | Oasisbr |
| Resumo: | This report describes an algorithm for the Unbounded Knapsack Problem based on the algorithm EDUK (Efficient Dynamic Programming for the Unbounded Knapsack Problem). EDUK takes advantage of the problem properties of dominance and periodicity to speed up computation. This algorithm is compared with other implementations and it is tested both with randomly generated instances and with instances generated from a delayed column generation for the Cutting Stock Problem. This report also contains an analysis of unbounded knapsack instances. |
|---|
Atividades financiadas
Não foram encontrados projetos financiados.