An exact algorithm for large unbounded knapsack problems. Martello, S. & Toth, P. Oper Res Lett, 9(1):15–20, 1990.
doi  abstract   bibtex   
Given n types, each having an associated profit and weight, and a container of given capacity, the unbounded knapsack problem is to determine the number of items of each type to be selected so that the corresponding total profit is a maximum and the corresponding total weight does not exceed the capacity. We present upper bounds, dominance relations, and an approach–based on the definition of a core problem–to the exact solution of very large instances of the problem. We give the results of computational experiments on randomly generated test problems involving up to 250 000 item types.
@Article{martello90exact,
  author    = {Silvano Martello and Paolo Toth},
  title     = {An exact algorithm for large unbounded knapsack problems},
  journal   = {Oper Res Lett},
  year      = {1990},
  volume    = {9},
  number    = {1},
  pages     = {15--20},
  issn      = {0167-6377},
  abstract  = {Given n types, each having an associated profit and weight, and a container of given capacity, the unbounded knapsack problem is to determine the number of items of each type to be selected so that the corresponding total profit is a maximum and the corresponding total weight does not exceed the capacity. We present upper bounds, dominance relations, and an approach--based on the definition of a core problem--to the exact solution of very large instances of the problem. We give the results of computational experiments on randomly generated test problems involving up to 250 000 item types.},
  doi       = {10.1016/0167-6377(90)90035-4},
  keywords  = {integer programming, integer knapsack, unbounded integer knapsack},
  owner     = {Sebastian},
  timestamp = {2010.11.13},
}
Downloads: 0