×

zbMATH — the first resource for mathematics

Kernel search: a general heuristic for the multi-dimensional knapsack problem. (English) Zbl 1188.90207
Summary: We apply the kernel search framework to the solution of the strongly NP-hard multi-dimensional knapsack problem (MKP). Kernel search is a heuristic framework based on the identification of a restricted set of promising items (kernel) and on the exact solution of ILP sub-problems. Initially, the continuous relaxation of the MKP, solved on the complete set of available items, is used to identify the initial kernel. Then, a sequence of ILP sub-problems are solved, where each sub-problem is restricted to the present kernel and to a subset of other items. Each ILP sub-problem may find better solutions with respect to the previous one and identify further items to insert into the kernel. The kernel search was initially proposed to solve a complex portfolio optimization problem. In this paper we show that the method has general key features that make it appropriate to solve other combinatorial problems using binary variables to model the decisions to select or not items. We adapt the kernel search to the solution of MKP and show that the method is very effective and efficient with respect to known problem-specific approaches. Moreover, the best known values of some MKP benchmark problems from the MIPLIB library have been improved.

MSC:
90C27 Combinatorial optimization
90C59 Approximation methods and heuristics in mathematical programming
Software:
MIPLIB; Knapsack
PDF BibTeX Cite
Full Text: DOI
References:
[1] Angelelli E, Mansini R, Speranza MG. Kernel Search: a heuristic framework for MILP problems with binary variables. Technical Report of the Department of Electronics for Automation, University of Brescia, R.T. 2007-04-56, December 2007.
[2] Balas, E.; Zemel, E., An algorithm for large zero – one knapsack problems, Operations research, 28, 1130-1154, (1980) · Zbl 0449.90064
[3] Boussier S, Vasquez M, Vimont Y, Hanafi S, Michelon P. Solving the 0-1 multidimensional knapsack problem with resolution search. In: Workshop on Applied Combinatorial Optimization (VI ALIO/EURO) Buenos Aires, Argentina, December 2008. · Zbl 1185.90170
[4] Chu, P.C.; Beasley, J.E., A genetic algorithm for the multidimensional knapsack problem, Journal of heuristics, 4, 63-86, (1998) · Zbl 0913.90218
[5] Gomes da Silva C, Climaco J, Figueira J. Core problems in bi-criteria 0,1-knapsack: new developments. Technical Report 12/2005, 2005 INESC-Coimbra. · Zbl 1169.90439
[6] Drexl, A., A simulated annealing approach to the multiconstraint zero – one knapsack problem, Computing, 40, 1-8, (1988) · Zbl 0638.65053
[7] Fleszar, K.; Hindi, K.S., Fast, effective heuristics for the 0-1 multi-dimensional knapsack problem, Computers & OR, 36, 5, 1602-1607, (2009) · Zbl 1179.90282
[8] Gilmore, P.C.; Gomory, R.E., The theory and computation of knapsack functions, Operations research, 14, 1045-1075, (1966) · Zbl 0173.21502
[9] Glover, F.; Kochenberger, G.A., Critical event tabu search for multidimensional knapsack problems, (), 407-427 · Zbl 0877.90055
[10] Hanafi, S.; FrĂ©ville, A., An efficient tabu search approach for the 0-1 multidimensional knapsack problem, European journal of operational research, 106, 659-675, (1998) · Zbl 0991.90089
[11] Kellerer, H.; Pferschy, U.; Pisinger, D., Knapsack problems, (2004), Springer Berlin, Germany · Zbl 1103.90003
[12] Mansini, R.; Speranza, M.G., A multidimensional knapsack model for the asset-backed securitization, Journal of the operational research society, 53, 822-832, (2002) · Zbl 1130.90391
[13] Pisinger, D., Core problems in knapsack algorithms, Operations research, 47, 570-575, (1999) · Zbl 0979.90091
[14] Puchinger J, Raidl GR, Pferschy U. The core concept for the multidimensional knapsack problem. In Proceedings of the 6th European conference on evolutionary computation in combinatorial optimization (EvoCOP 06). Lecture notes in computer science, vol. 3906. Berlin: Springer; 2006. p. 195-208. · Zbl 1401.90198
[15] Shih, W., A branch and bound method for the multiconstraint zero – one knapsack problem, Journal of the operational research society, 30, 369-378, (1979) · Zbl 0411.90050
[16] Vasquez, M.; Vimont, Y., Improved results on the 0-1 multidimensional knapsack problem, European journal of operational research, 165, 70-81, (2005) · Zbl 1112.90366
[17] Vimont, Y.; Boussier, S.; Vasquez, M., Reduced costs propagation in an efficient implicit enumeration for the 0-1 multidimensional knapsack problem, Journal of combinatorial optimization, 15, 165-178, (2008) · Zbl 1138.90014
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.