  This work presents an empirical analysis of exact algorithms for the
unbounded knapsack problem, which includes seven algorithms from the
literature, two commercial solvers, and more than ten thousand instances. The
terminating step-off, a dynamic programming algorithm from 1966, presented the
lowest mean time to solve the most recent benchmark from the literature. The
threshold and collective dominances are properties of the unbounded knapsack
problem first discussed in 1998, and exploited by the current state-of-the-art
algorithms. The terminating step-off algorithm did not exploit such dominances,
but has an alternative mechanism for dealing with dominances which does not
explicitly exploits collective and threshold dominances. Also, the pricing
subproblems found when solving hard cutting stock problems with column
generation can cause branch-and-bound algorithms to display worst-case times.
The authors present a new class of instances which favors the branch-and-bound
approach over the dynamic programming approach but do not have high amounts of
simple, multiple and collective dominated items. This behaviour illustrates how
the definition of hard instances changes among algorithm approachs. The codes
used for solving the unbounded knapsack problem and for instance generation are
all available online.
