Knapsack Problems
I. History
1.1 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.
1.2 Type of knapsack problems
1.2.1 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 :
(1) 0-1Knapsack problem
(2) Bounded knapsack problem
(3) Subset-sum problem
(4) Change-making problem
1.2.2 Multiple knapsack problems
Wich there are more than one container is available.
The problems considered :
(1) 0-1Multiple knapsack problem
(2) Genwealized assignment problem
(3) Bin-packing problem
II. 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 and the problem is to select a subset of the items whose total weight does not exceed c and whose total profit is a maximum.
We assume, without loss of generality, that all input data are positive integers. Introducing the binary decision variables xj, with xj = 1 if item j is selected, and xj =0 otherwise, we get the integer linear programming (ILP) model:
where all data are positive integers. In the following we will denote the Knapsack Problem by KP. Without loss of generality we may assume that wj <c for j = 1,...,n, to ensure that each item considered fits into the knapsack, and that to avoid trivial solutions.
2.2 Different formulations of the knapsack problem:
2.2.1 Branch and bound algorithm
A branch and bound method is basically characterized by two decision rules. One provides a procedure for the estimation of the upper bound of the objective function at a node; and the other specifies a choice criterion for the selection of a branching variable at the node selected for further partitioning. The following decision rules will be adopted to effect the search process.
(i) The estimation of the upper bound.
(ii) The choice of a branching variable.
2.2.2 Dynamic programming
New dynamic programming algorithms for the solution of the Zero-One Knapsack Problem are developed. Original recursive procedures for the computation of the Knapsack Function are presented and the utilization of bounds to eliminate states not leading to optimal solutions is analyzed. The proposed algorithms, according to the nature of the problem to be solved, automatically determine the most suitable procedure to be employed. Extensive computational results showing the efficiency of the new and the most commonly utilized algorithms are given. The results indicate that, for difficult problems, the algorithms proposed are superior to the best branch and bound and dynamic programming methods.
III. Applications
3.1 Problem Description:
Many industrial problems can be formulated as Knapsack Problems: Cargo loading, cutting stock, project selection, and budget control to mention a few examples. Many combinatorial problems can be reduced to KP, and KP arises also as a subproblem in several algorithms of integer linear programming.
3.1.1 Example of a real life application
0-1 knapsack problem
A vendor car has capacity K kg. There are some bundles having respective weights cl, c2, …, cn kg which are to be transported by that vendor car. The problem is to pick up those bundles and load them in the car so that the car capacity is maximum utilized, if not fully.
Subset-sum problem
The maximum subset sum problem has a wide range of important applications. Example fields are material, transportation, television and radio industries, and computer system resource allocation. In addition, the problem also models static job scheduling in a multiprogrammed parallel system. In such a system, there are M identical processors. Assume that we are given a set S of n jobs J1, J2,…, Jn, where job Ji requires xi processors for parallel execution. The problem here is to find a subset S’ of jobs to execute simultaneously in such a way that system utilization is maximized. Furthermore, we try to schedule as many jobs as possible to maximize system throughput.
Multip-choice knapsack problem
In a restaurant, where a person has to choose k course, without surpassing the amount of c calories, his diet prescribes. Assuming that here are Ni dishes to choose among for each among for each course i=1,…,k, and wij is the nutritive value while pij is a rating saying how well each dish tastes. Then an optimal meal may be found by solving the Multiple-choice Knapsack problem.
The Bin-packing problem
It has been applied for cutting iron bars in a kibbutz, in order to minimize the number of bars used each day. Here wj is the length of each piece demanded, while c is the length of each bar, as delivered from the factory.
3.2 Literature application:
Application 1
Source:
Shih, W., 1979. A branch and bound method for the multiconstraint zero-one knapsack problem. Journal of the Operational Research Society, 30, 369-378.
Description:
Maximize: 84 x1 + 34x2 + 31x3 + 14x4 + 67x5 + 65X6 + 86x7 + 98X8 + 50x9 + 7x10
Subject to (1) 20 x1 + 12 x2 + 7x3 + 75x4 + 93x5 + 21 x6 + 75x7
+ 67 x8 + 34x9 + 28x10 190 lbs.
(2) 41 x1 + 51 x2 + 24 x3 + 40 x4 + 84 x5 + 70 x6 + 34 x7
+ 41 x8 + 49 x9 + 27 x10 250 cubic feet
and xj = 0,1; j=1,2,...,10;
where
Application 2
Source:
Labbe, M., Laporte, G., Martello, S., 1995. An exact algorithm for the dual bin packing problem. Operation research letter, 17, 9-18.
Description:
For every value of n = 10, 20, 40, 60, 80, 100 and c = 100, 120, 150, 200, 300, 400, 500, item weights were generated in each of the three intervals [a, 99], with a= 1, 20 and 50, according to a discrete uniform distribution, and discarding instances not satisfying . No instances were generated for the combination n = 10 and c = 500 since cannot be satisfied in this case. For each of the 123 feasible combinations of n, c and a, 10 instances were randomly generated.
Application 3
Source:
Pisinger, D., 1995. An expanding-core algorithm for the exact 0-1 Knapsack Problem. European journal of operational research, 87, 175-187.
Description:
Four types of randomly generated data instances are considered as listed below. Each type will be tested with data-range R = 100, 1000, 10000 for different problem sizes n = 50, 100, 200, 500, 1000, 2000, 5000, 10000, 20000, 50000, 100000. The capacity c is chosen as c.
• uncorrelated data instances (uc): pj and wj are randomly distributed in [1, R];
• weakly correlated data instances (we): wj randomly distributed in [1, R] and Pj randomly distributed in such that;
• strongly correlated data instances (sc): wj randomly distributed in [1, R] and pj = wj + 10;
• subset-sum data instances (ss): wj randomly distributed in [1, R] and pj =wj.
For each problem type, size and range, we construct and solve 50 different data instances. The presented results are average values. If some data instance was not solved within 1 hour the field is marked with a ,_,.
Application 4
Source:
Soma, N.Y., Toth, P., 2002. An exact algorithm for the subset sum problem. European journal of operation research, 136, 57-66.
Description:
Problem P(E). Given a postitive integer E, the weights wi’s are randomly distributed in [1, 10E] and c=[n10E/4]. We consider E=3 and E=6
Problems even-odd. wi’s even, randomly distributed [1,104], c=2[n104/8]+1 (odd).
Problems F2(E, v, ). Given three positive integers E, v,, find a pair (a0, a1) =1, c=(a0-1)( (a1-1)-1, and . We consider E=3, v=5, =50. The coefficients wi’s are defined by:
Problems F2(E, v, ) have no optimal solution of value z=c, indeed it is well known that a0y1+a1y2=(a0-1)( (a1-1)-1, gcd (a0, a1) =1 has no positive integer solutions (in y1 and y2), since it is the exact Frobenius bound for the linear Diophantine equation with two variable. Incidentally, it is also well known that the determination of such bound is NP-Hard.
IV. Reference
[1] Li, K., 1998. Average-case performance analysis of an approximation algorithm for maximum subset sum using recurrence relations. Computers math, 36(6), 63-75.
[2] Martello,S., Toth, P. 1990. Knapsack problems: algorithms and computer implementations. John Wiley & Sons.
[3] Martello,S., Pisinger, D., 2000. New trends in exact algorithms for the 0-1 knapsack problem. European journal of operational research, 123, 325-332.
[4] Pisinger, D., 1995. Algorithm for knapsack problem.
[5] Pisinger, D., 1995 An expanding-core algorithm for the exact 0-1 Knapsack problem. European journal of operational research, 87(1), 175-187.
[6] Shih, W., 1979. A branch and bound method for the multiconstraint zero-one knapsack problem. Journal of the Operational Research Society, 30, 369-378.
[7] Sinha, P., Zolters A.A., 1979. The multiple-choice knapsack problem. Operation research, 27(3), 503-515.
[8] Sinuany-Stern, Z., Weiner, I., 1994. The one dimensional cutting stock problem using two objectives, Journal of the operational research society, 45(2), 231-236.