Abstract
The multiconstraint 0–1 knapsack problem encounters when deciding how to use a knapsack with multiple resource constraints. The problem is known to be NP-hard, thus a “good” algorithm for its optimal solution is very unlikely to exist. We show how the concept of simulated annealing may be used for solving this problem approximately. 57 data sets from literature demonstrate, that the algorithm converges very rapidly towards the optimum solution.
Zusammenfassung
Mehrfach beschränkte binäre Knapsack-Probleme erfordern Engpaßentscheidungen unter Berücksichtigung zahlreicher Ressourcenbeschränkungen. Angesichts der NP-Schwierigkeit ist die Existenz eines „guten” Optimierungsverfahrens zu seiner Lösung sehr unwahrescheinlich. Wir zeigen, wie das Problem mit Hilfe des Konzeptes der simulierten Abkühlung näherungsweise gelöst werden kann. 57 Datensätze aus der Literatur verdeutlichen, daß das Verfahren sehr schnell gegen die optimale Lösung konvergiert.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Aho, A. V., Hopcroft, J. E., Ullman, J. D.: Data Structures and Algorithms. Reading, Mass.: Addison-Wesley Publishing Company 1983.
Balas, E., Martin, C. H.: Pivot and complement — a heuristic for 0–1 programming. Management Science26, 86–96 (1980).
Balas, E., Zemel, E.: Solving large zero-one knapsack problems. Operations Research28, 1130–1154 (1980).
Bonomi, E., Lutton, J.-L.: The asymptotic behaviour of quadratic sum assignment problems: a statistical mechanics approach. European J. of Operational Research26, 295–300 (1986).
Burkard, R. E., Rendl, F.: A thermodynamically motivated simulation procedure for combinatorial optimization problems. European J. of Operational Research17, 169–174 (1984).
Somschke, W.: Minimierung der Wartezeiten für Umsteiger im öffentlichen Nahverkehr. Forthcoming in OR Spektrum.
Freville, A., Plateau, G.: Méthodes heuristiques performantes pour les problèmes en variables 0–1 à plusieurs constraintes en ińegalité. Publication ANO-91, Université des Sciences et Techniques de Lille 1982.
Freville, A., Plateau, G.: Heuristics and reduction methods for multiple constraints 0–1 linear programming problems. European J. of Operational Research24, 206–215 (1986).
Freville, A., Plateau, G.: Hard 0–1 multiknapsack test problems for size reduction methods. Prepublications informatique 72, Université Paris-Nord 1987.
Frieze, A. M., Clarke, M. R. B.: Approximation algorithms for them-dimensional 0–1 knapsack problem. Worst-case and probabilistic analyses. European J. of Operational Research15, 100–109 (1984).
Garey, M., Johnson, D.: Computers and Intractability: a Guide to the Theory of NP-Completeness. San Francisco: Freeman 1979.
Gavish, B., Pirkul, H.: Efficient algorithms for solving multiconstraint zero-one knapsack problems to optimality. Math. Programming31, 78–105 (1985).
van Laarhoven, P. J. M., Aarts, E. H. L.: Simulated Annealing: Theory and Applications. Dordrecht: D. Reidel Publishing Company 1987.
Lorie, J., Savage, L. J.: Three problems in capital rationing. J. of Business28, 229–239 (1955).
Loulou, R., Michaelides, E.: New greedy-like heuristics for the multidimensional 0–1 knapsack problem. Operations Research27, 1101–1114 (1979).
Magazine, M. J., Oguz, O.: A heuristic algorithm for the multidimensional zero-one knapsack problem. European J. of Operational Research16, 319–326 (1984).
Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N., Teller, A. H., Teller, E.: Equation of state calculation by fast computing machines. J. of Chemical Physics21, 1087–1092 (1953).
Petersen, C. C.: Computational experience with variants of the Balas algorithm applied to the selection of R&D projects. Management Science13, 736–750 (1967).
Rossier, Y., Troyon, M., Liebling, Th. M.: Probabilistic exchange algorithms and euclidean traveling salesman problems. OR Spektrum8, 151–164 (1986).
Senyu, S., Toyoda, Y.: An approach to linear programming with 0–1 variables. Management Science15, B196-B207 (1968).
Shih, W.: A branch and bound method for the multiconstraint zero-one knapsack problem. J. Opl. Res. Soc.30, 369–378 (1979).
Telley, H., Liebling, Th. M., Mocellin, A.: Reconstruction of polycristalline structures: a new application of combinatorial optimization. Computing38, 1–11 (1987).
Toyoda, Y.: A simplified algorithm for obtaining approximate solutions to zero-one programming problems. Management Science21, 1417–1427 (1975).
Weber, M., Liebling, Th. M.: Euclidean matching problems and Metropolis algorithms. Zeitschrift für Operations Research30, A85-A110 (1986).
Weingartner, H. M., Ness, D. N.: Methods for the solution of the multi-dimensional 0/1 knapsack problem. Operations Research15, 83–103 (1967).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Drexl, A. A simulated annealing approach to the multiconstraint zero-one knapsack problem. Computing 40, 1–8 (1988). https://doi.org/10.1007/BF02242185
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF02242185