Abstract
We present the newly developed core concept for the Multidimensional Knapsack Problem (MKP) which is an extension of the classical concept for the one-dimensional case. The core for the multidimensional problem is defined in dependence of a chosen efficiency function of the items, since no single obvious efficiency measure is available for MKP. An empirical study on the cores of widely-used benchmark instances is presented, as well as experiments with different approximate core sizes. Furthermore we describe a memetic algorithm and a relaxation guided variable neighborhood search for the MKP, which are applied to the original and to the core problems. The experimental results show that given a fixed run-time, the different metaheuristics as well as a general purpose integer linear programming solver yield better solution when applied to approximate core problems of fixed size.
This work is supported by RTN ADONET under grant 504438 and the Austrian Science Fund (FWF) under grant P16263-N04.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
We’re sorry, something doesn't seem to be working properly.
Please try refreshing the page. If that doesn't work, please contact support so we can address the problem.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Balas, E., Zemel, E.: An algorithm for large zero-one knapsack problems. Operations Research 28, 1130–1154 (1980)
Bertsimas, D., Tsitsiklis, J.N.: Introduction to Linear Optimization. Athena Scientific (1997)
Chu, P.C., Beasley, J.: A genetic algorithm for the multiconstrained knapsack problem. Journal of Heuristics 4, 63–86 (1998)
Fréville, A., Plateau, G.: An efficient preprocessing procedure for the multidimensional 0–1 knapsack problem. Discrete Applied Mathematics 49, 189–212 (1994)
Glover, F., Kochenberger, G.: Critical event tabu search for multidimensional knapsack problems. In: Osman, I., Kelly, J. (eds.) Metaheuristics: Theory and Applications, pp. 407–427. Kluwer Academic Publishers, Dordrecht (1996)
Gottlieb, J.: On the effectivity of evolutionary algorithms for multidimensional knapsack problems. In: Fonlupt, C., Hao, J.-K., Lutton, E., Schoenauer, M., Ronald, E. (eds.) AE 1999. LNCS, vol. 1829, pp. 22–37. Springer, Heidelberg (2000)
Hansen, P., Mladenović, N.: An introduction to variable neighborhood search. In: Voss, S., Martello, S., Osman, I., Roucairol, C. (eds.) Metaheuristics, Advances and Trends in Local Search Paradigms for Optimization, pp. 433–458. Kluwer, Dordrecht (1999)
Kellerer, H., Pferschy, U., Pisinger, D.: Knapsack Problems. Springer, Heidelberg (2004)
Martello, S., Toth, P.: A new algorithm for the 0-1 knapsack problem. Management Science 34, 633–644 (1988)
Pirkul, H.: A heuristic solution procedure for the multiconstraint zero-one knapsack problem. Naval Research Logistics 34, 161–172 (1987)
Pisinger, D.: An expanding-core algorithm for the exact 0–1 knapsack problem. European Journal of Operational Research 87, 175–187 (1995)
Pisinger, D.: A minimal algorithm for the 0–1 knapsack problem. Operations Research 45, 758–767 (1997)
Pisinger, D.: Core problems in knapsack algorithms. Operations Research 47, 570–575 (1999)
Puchinger, J., Raidl, G.R.: Relaxation guided variable neighborhood search. In: Hansen, P., Mladenović, N., Pérez, J.A.M., Batista, B.M., Moreno-Vega, J.M. (eds.) Proceedings of the 18th Mini Euro Conference on Variable Neighborhood Search, Tenerife, Spain (2005)
Raidl, G.R.: An improved genetic algorithm for the multiconstrained 0–1 knapsack problem. In: Fogel, D., et al. (eds.) Proceedings of the 5th IEEE International Conference on Evolutionary Computation, pp. 207–211. IEEE Press, Los Alamitos (1998)
Raidl, G.R., Gottlieb, J.: Empirical analysis of locality, heritability and heuristic bias in evolutionary algorithms: A case study for the multidimensional knapsack problem. Evolutionary Computation Journal 13(4) (to appear, 2005)
Senju, S., Toyoda, Y.: An approach to linear programming with 0–1 variables. Management Science 15, 196–207 (1968)
Vasquez, M., Hao, J.-K.: A hybrid approach for the 0–1 multidimensional knapsack problem. In: Proceedings of the Int. Joint Conference on Artificial Intelligence 2001, pp. 328–333 (2001)
Vasquez, M., Vimont, Y.: Improved results on the 0-1 multidimensional knapsack problem. European Journal of Operational Research 165, 70–81 (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Puchinger, J., Raidl, G.R., Pferschy, U. (2006). The Core Concept for the Multidimensional Knapsack Problem. In: Gottlieb, J., Raidl, G.R. (eds) Evolutionary Computation in Combinatorial Optimization. EvoCOP 2006. Lecture Notes in Computer Science, vol 3906. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11730095_17
Download citation
DOI: https://doi.org/10.1007/11730095_17
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-33178-0
Online ISBN: 978-3-540-33179-7
eBook Packages: Computer ScienceComputer Science (R0)Springer Nature Proceedings Computer Science
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
