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 ite ms whose weight sum does not exceed a prescribed capacity and whose value i s maximum. The specific problem that arises depends on the number of knapsa cks (single or multiple) to be filled and on the number of available items of each type (bounded or unbounded). The classical 0-1Knapsack Problem aris es when there is one knapsack and one item of each type. This paper conside rs a number of hard Knapsack Problems with a single constraint. We discuss a number of specialized algorithms which we have recently developed. Our wo rk focuses on the 0-1Knapsack Problem, and the Bounded Knapsack Problem, th e Unbounded Knapsack Problem.