Computational aspects of hard Knapsack Problems

The Knapsack Problems are among the simplest integer programs which are NP-hard. Problems in this class are typically concerned with selecting from a set of given items, each with a specified weight and value, a subset of items whose weight sum does not exceed a prescribed capacity and whose value is maximum. The specific problem that arises depends on the number of knapsacks (single or multiple) to be filled and on the number of available items of each type (bounded or unbounded). The classical 0-1Knapsack Problem arises when there is one knapsack and one item of each type. This paper considers a number of hard Knapsack Problems with a single constraint. We discuss a number of specialized algorithms which we have recently developed. Our work focuses on the 0-1Knapsack Problem, and the Bounded Knapsack Problem, the Unbounded Knapsack Problem.