Abstract
The Knapsack problem (maximize a linear function, subject to a unique constraint, all being in integers), although of thenp-complete type, is a well solved case in combinatorial programming.
The reason for this is twofold:
-
(i)
an upper bound of the objective function is easy to compute
-
(ii)
it is quite simple to construct feasible solutions. They give lower bounds of the optimum. This makes it possible to know rapidly the optimal value of many variables, and therefore to reduce the problem. Several studies have appeared recently on the subject [5, 9, 12, 18]. We present a program by which Knapsacks involving up to 60 000 boolean variables were solved in a matter of seconds, on an I.B.M. 370-168.
Similar content being viewed by others
References
E. Balas, “Discrete programming by the filter method”,Operations Research 15 (1975) 915–957.
G.H. Bradley, “Transformation of integer programs to knapsack problems”,Discrete Mathematics 1 (1) (May 1971) 29–45.
R.S. Dembro and L.H. Hammer, “A reduction algorithm for knapsack problems”, Department of Combinatorics and Optimization, Research Report CORR, University of Waterloo, Ontario, Canada (1975).
B. Faaland, “On the number of solutions to a diophantine equation”,Journal of Combinatorial Theory (A) 13 (1972) 170–175.
D. Fayard and G. Plateau, “Resolution of the 0–1 knapsack problem: Comparison of Methods”,Mathematical Programming 8 (3) (1975) 272–307.
R.S. Garfinkel and G.L. Nemhauser,Integer Programming (Wiley Interscience Publication 1972).
P.C. Gilmore and R.E. Gomory, “The theory and computation of knapsack functions”,Operations Research 14 (1966) 1045–1074.
M. Gondran, “Un outil pour la programmation en nombres entiers: la méthode des congruences décroissantes”,Revue française d'Automatique Informatique, Recherche opérationnelle, Revue verte, AFCET 3 (Sept. 1973) 35–54.
H. Greenberg and R.L. Hegerich, “A branch search algorithm for the knapsack problem”,Management Science 16 (5) (1970) 327–332.
P. Hansen, “Programmes mathématiques en variables 0–1”, Thèse d'agrégation, Bruxelles, Belgique (1974).
D.S. Hirschberg and C.K. Wong, “A polynomial time algorithm for the knapsack problem with two variables”,Journal of the Association for Computing Machinery 23 (1) (Jan. 1976) 147–154.
G.P. Ingargiola and J.F. Korsh, “Reduction algorithm for zero–one single knapsack problems”,Management Science 20 (4), part 1 (1973) 460–463.
P.J. Kolesar, “A branch and bound algorithm for the knapsack problem”,Management Science 13 (19) (1967) 723–735.
R. Krawczyk, “Ein Verfahren zur Lösung des bivalenten Knapsackproblems”,Angewandte Informatik 5 (1972) 223–228.
T.A. Lambe, “Bounds on the numbers of the feasible solutions to a knapsack problem”,SIAM Journal on Applied Mathematics 26 (2) (1974) 302–305.
M. Laurière, “Une méthode de résolution rapide pour le problème du knapsack”, Thèse 3ème cycle, Paris, France (1976).
R.M. Nauss, “An officient algorithm for the 0–1 knapsack problem”,Management Science 23 (1) (Sept. 1976) 27–31.
S. Sahni, “Approximate algorithms for the 0–1 knapsack problem”,Journal of the Association for Computing Machinery 22 (1) (1975) 115–124.
Saunders and Schinzinger, “A shrinking boundary algorithm for discrete system models”,I.E.E., Transactions on Systems Science and Cybernetics, SSC-6 (2) (1970) 133–140.
S. Martello and P. Toth, “The 0–1 Knapsacle problem”, Summer school in combinatorial optimization, Sogesta, Urbino, Instituto di Automatica, University of Bologna, Italy (May, June 1977).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Lauriere, M. An algorithm for the 0/1 Knapsack problem. Mathematical Programming 14, 1–10 (1978). https://doi.org/10.1007/BF01588947
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01588947