(knapsack problem)(knapsack problem).doc

Knapsack Problems History Introduction Knapsack Problems have been intensively studied since the pioneering work of Dantzig in the late 50’s, both because of their immediate applications in industry and financial management, but more pronounced for theoretical reasons, as Knapsack Problems frequently occur by relaxation of various integer programming problems. In such application, we need to solve a Knapsack Problem each time a bounding function is derived, demanding extremely fast solution techniques. The family of Knapsack Problems all requires a subset of some given items to be chosen such that the corresponding profits sum is maximized without exceeding the capacity of the knapsack(s). Different types of Knapsack Problems occur, depending on the distribution of the items and knapsacks: In the 0-1Knapsack Problem each item may be chosen at most once, while in the Bounded Knapsack Problem we have a bounded amount of each item type. The Multiple-choice Knapsack Problem occurs when the items should be chosen from disjoint classes and, if several knapsacks are to be filled simultaneously, we get the Multiple Knapsack Problem. The most general form is the Multi-constrained Knapsack Problem, which basically is a general Integer Programming (IP) Problem with positive coefficients. Type of knapsack problems Single knapsack problems There is one container (or knapsack) must be filled with an optimal subset of items. The capacity of such a container will be denoted by c. The problems considered : 0-1Knapsack problem Bounded knapsack problem Subset-sum problem Change-making problem Multiple knapsack problems Wich there are more than one container is available. The problems considered : 0-1Multiple knapsack problem Genwealized assignment problem Bin-packing problem Problem Definition: 2.1 Problem Model: We consider the classical 0-1 knapsack problem (KP) where a subset of n given items has to be packed in a knapsack of capacity c. Each item has a profit pj and a weight wj