×

Improved results on the 0–1 multidimensional knapsack problem. (English) Zbl 1112.90366

Summary: Geometric Constraint and Cutting planes have been successfully used to solve the 0-1 multidimensional knapsack problem. Our algorithm combines Linear Programming with an efficient tabu search. It gives best results when compared with other algorithms on benchmarks issued from the OR-L\(_{IBRARY}\). Embedding this algorithm in a variables fixing heuristic still improves our previous results. Furthermore difficult sub problems with about 100 variables issued from the 500 original ones could be generated. These small sub problems are always very hard to solve.

MSC:

90C09 Boolean programming
90C27 Combinatorial optimization
90C59 Approximation methods and heuristics in mathematical programming
90C10 Integer programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Balas, E.; Martin, C. H., Pivot and complement a heuristic for 0-1 programming, Management Science, 26, 86-96 (1980) · Zbl 0442.90060
[2] Chu, P. C.; Beasley, J. E., A genetic algorithm for the multidimensional knapsack problem, Journal of Heuristic, 4, 63-86 (1998) · Zbl 0913.90218
[3] Chvátal, V., Linear Programming (1983), W.H. Freeman and Company · Zbl 0318.05002
[4] Dammeyer, F.; Voß, S., Dynamic tabu list management using the reverse elimination method, Annals of Operations Research, 41, 31-46 (1993) · Zbl 0775.90290
[5] Drexl, A., A simulated annealing approach to the multiconstraint zero-one knapsack problem, Computing, 40, 1-8 (1988) · Zbl 0638.65053
[6] Fréville, A.; Plateau, G., Sac à dos multidimensionnel en variable 0-1: Encadrement de la somme des variables à l’optimum, Recherche Opérationnelle, 27, 2, 169-187 (1993) · Zbl 0777.90032
[7] Fréville, A.; Plateau, G., An efficient preprocessing procedure for the multidimensional 0-1 knapsack problem, Discrete Applied Mathematics, 49, 189-212 (1994) · Zbl 0802.90077
[8] Gavish, B.; Pirkul, H., Allocation of data bases and processors in a distributed computing system, Management of Distributed Data Processing, 31, 215-231 (1982)
[9] Gavish, B.; Pirkul, H., Efficient algorithms for solving multiconstraint zero-one knapsack problems to optimality, Mathematical Programming, 31, 78-105 (1985) · Zbl 0571.90065
[10] Glover, F., Tabu search, ORSA Journal of Computing, 2, 4-32 (1990) · Zbl 0771.90084
[11] Glover, F.; Kochenberger, G. A., Critical event tabu search for multidimensional knapsack problems, (Osman, I. H.; Kelly, J. P., Metaheuristics: The Theory and Applications (1996), Kluwer Academic Publishers), 407-427 · Zbl 0877.90055
[12] 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
[13] Hill, R. R.; Reilly, C. H., The effects of coefficient correlation structure in two dimensional knapsack problems on solution procedure performance, Management Science, 46, 2, 302-317 (2000) · Zbl 1231.90323
[14] Martello, S.; Toth, P., Knapsack Problems: Algorithms and Computer Implementations (1990), John Wiley · Zbl 0708.68002
[15] M.A. Osorio, F. Glover, P. Hammer, Cutting and surrogate constraint analysis for improved multidimensional knapsack solutions, Technical Report HCES-08-00, Hearin Center For Enterprise Science, The University of Mississippi, August 2000; M.A. Osorio, F. Glover, P. Hammer, Cutting and surrogate constraint analysis for improved multidimensional knapsack solutions, Technical Report HCES-08-00, Hearin Center For Enterprise Science, The University of Mississippi, August 2000 · Zbl 1028.90042
[16] 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
[17] M. Vasquez, Résolution en variables 0-1 de problèmes combinatoires de grande taille par la méthode tabou, PhD thesis, Université d’Angers U.F.R. Sciences, December 2000; M. Vasquez, Résolution en variables 0-1 de problèmes combinatoires de grande taille par la méthode tabou, PhD thesis, Université d’Angers U.F.R. Sciences, December 2000
[18] M. Vasquez, J.K. Hao, A hybrid approach for the 0-1 multidimensionnal knapsack problem, in: IJCAI-01 Proceedings of the 7th International Joint Conference on Artificial Intelligence, vol. 1, Seattle, Washington, USA, August 2001, pp. 328-333; M. Vasquez, J.K. Hao, A hybrid approach for the 0-1 multidimensionnal knapsack problem, in: IJCAI-01 Proceedings of the 7th International Joint Conference on Artificial Intelligence, vol. 1, Seattle, Washington, USA, August 2001, pp. 328-333
[19] Vasquez, M.; Hao, J. K., Une approche hybride pour le sac à dos multidimensionnel en variables 0-1, RAIRO Operations Research, 35, December, 415-438 (2001) · Zbl 1015.90056
[20] O. Wendt, W. König, Cooperative simulated annealing: How much cooperation is enough? Technical Report, Institute of Information Systems, Goethe University, Frankfurt, 1997; O. Wendt, W. König, Cooperative simulated annealing: How much cooperation is enough? Technical Report, Institute of Information Systems, Goethe University, Frankfurt, 1997
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.