Publication
An efficient dynamic programming algorithm for the Unbounded Knapsack Problem
| Summary: | 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. |
|---|---|
| Main Authors: | Moura, Leonardo Fernando dos Santos |
| Subject: | Algoritmos Gramatica : Grafos Unbounded knapsack problem Cutting stock problem Column generation |
| Year: | 2013 |
| Country: | Brazil |
| Document type: | bachelor thesis |
| Access type: | open access |
| Associated institution: | IBICT |
| Language: | English |
| Origin: | Oasisbr |
Funded activities
No funded projects found.