×

An efficient tabu search approach for the 0-1 multidimensional knapsack problem. (English) Zbl 0991.90089

Summary: We describe a new approach to tabu search (TS) based on strategic oscillation and surrogate constraint information that provides a balance between intensification and diversification strategies. New rules needed to control the oscillation process are given for the 0-1 multidimensional knapsack (0-1 MKP). Based on a portfolio of test problems from the literature, our method obtains solutions whose quality is at least as good as the best solutions obtained by previous methods, especially with large scale instances. These encouraging results confirm the efficiency of the tunneling concept coupled with surrogate information when resource constraints are present.

MSC:

90C09 Boolean programming
90B40 Search theory

Software:

Tabu search
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aboudi, R.; Jörnsten, K., Tabu search for general zero-one integer programs using the pivot and complement heuristic, ORSA Journal of Computing, 6, 82-93 (1994) · Zbl 0798.90105
[2] Balas, E.; Martin, C. H., Pivot and complement — A heuristic for 0-1 programming, Management Science Research, 26, 86-96 (1980) · Zbl 0442.90060
[3] Battiti, R., Reactive search: towards self-tuning heuristics, (Congress of Applied Decision Technologies. Congress of Applied Decision Technologies, Brunel, London, UK (1995))
[4] Battiti, R.; Tecchiolli, G., The reactive tabu search, ORSA Journal on Computing, 6, 126-140 (1994) · Zbl 0807.90094
[5] Battiti, R.; Tecchiolli, G., Local search with memory: benchmarking RTS OR Spectrum, 17, 67-86 (1995) · Zbl 0843.90094
[6] Bellman, R., Dynamic Programming (1957), Princeton University Press: Princeton University Press Princeton, NJ · Zbl 0077.13605
[7] Chajakis, E. D.; Guignard, M., A model for delivery of groceries in vehicles with multiple compartments and Lagrangean approximation schemes, (Congreso Latino Ibero-Americano de Investigation de Operaciones e Ingenieria de Sistemas. Congreso Latino Ibero-Americano de Investigation de Operaciones e Ingenieria de Sistemas, Mexico City (1992))
[8] Charon, I.; Hudry, O., The noising method: A new method for combinatorial optimization, Operations Research Letters, 133-137 (1993) · Zbl 0798.90118
[9] Dammeyer, F.; Voβ, S., Dynamic tabu list management using the reverse elimination method, Annals of Operations Research, 41, 31-46 (1993) · Zbl 0775.90290
[10] Drexl, A., A simulated annealing approach to the multiconstraint zero-one knapsack problem, Computing, 40, 1-8 (1988) · Zbl 0638.65053
[11] Dueck, G., New optimization heuristics — The great deluge algorithm and the record-to-record travel, IBM Technical report TR 89.06/011 (1989) · Zbl 0773.65042
[12] Dueck, G.; Scheurer, T., Threshold accepting: a general purpose optimization algorithm, Journal of Computational Physics, 90, 161-175 (1990) · Zbl 0707.65039
[13] Dyer, H. E., Calculating surrogate constraints, Mathematical Programming, 12, 255-278 (1980) · Zbl 0464.90067
[14] Fayard, D.; Plateau, G., An exact algorithm for the 0-1 collapsing knapsack problem, Discrete Applied Mathematics, 49, 175-187 (1994) · Zbl 0806.90089
[15] Feo, T. A.; Resende, M. G.C.; Smith, S. H., A greedy randomized adaptive search for maximum independent set, Operations Research, 42, 860 (1994) · Zbl 0815.90121
[16] Freville, A., Contribution a l’Optimisation en Nombres Entiers, (Habilitation a Diriger des Recherches (1991), Universite de Paris XIII: Universite de Paris XIII France)
[17] Freville, A.; Plateau, G., Méthodes Heuristiques Performantes pour les Programmes en Variables 0-1, (Working paper, ANO-91 (1982), Universite des Sciences et Techniques de Lille: Universite des Sciences et Techniques de Lille France) · Zbl 0579.90066
[18] Freville, A.; Plateau, G., Heuristics and reduction methods for multiple constraints 0-1 linear programming problems, European Journal of Operational Research, 24, 206-215 (1986) · Zbl 0579.90066
[19] Freville, A.; Plateau, G., Hard 0-1 multiknapsack test problems for size reduction methods, Investigacion Operativa, 1, 251-270 (1990)
[20] Freville, A.; Plateau, G., An exact surrogate dual search for the 0-1 bidimensional knapsack problem, European Journal of Operational Research, 68, 413-421 (1993) · Zbl 0782.90069
[21] Freville, A.; Plateau, G., An efficient preprocessing procedure for the multidimensional 0-1 knapsack problem, Discrete Applied Mathematics, 49, 189-212 (1994) · Zbl 0802.90077
[22] Freville, A.; Plateau, G., The 0-1 bidimensional knapsack problem: towards an efficient high level primitive tool, Journal of Heuristics, 2, 147-167 (1996) · Zbl 0870.90084
[23] Gavish, B.; Pirkul, H., Allocation of databases and processors in a distributed data processing, (Akola, J., Management of Distributed Data Processing (1982), North Holland: North Holland Amsterdam), 215-231
[24] Gavish, B.; Pirkul, H., Models for computer and file allocation in distributed computer networks (1983), The Graduate School of Management, the University of Rochester, Working paper
[25] Gavish, B.; Pirkul, H., Efficient algorithms for solving multiconstraint zero-one knapsack problems to optimality, Mathematical Programming, 31, 78-105 (1985) · Zbl 0571.90065
[26] Gearing, C. E.; Swart, W. W.; Var, T., Determining the optimal investment policy for the tourism sector of a developing country, Management Science, 20, 487-497 (1973)
[27] Gilmore, P. C.; Gomory, R. E., The theory and computation of knapsack functions, Operations Research, 14, 1045-1074 (1966) · Zbl 0173.21502
[28] Glover, F., A multiphase dual algorithm for the 0-1 integer programming problem, Operations Research, 13, 879-919 (1965) · Zbl 0163.41301
[29] Glover, F., Heuristics for integer programming using surrogate constraints, Decision Sciences, 8, 156-166 (1977)
[30] Glover, F., Future paths for integer programming and links to artificial intelligence, Computers and Operations Research, 19, 533-549 (1986) · Zbl 0615.90083
[31] Glover, F., Tabu search, Part 1, ORSA Journal on Computing, 1, 190-206 (1989) · Zbl 0753.90054
[32] Glover, F., Tabu thresholding: improved search by nonmonotonic trajectories, ORSA Journal On Computing, 7, 426-442 (1995) · Zbl 0843.90097
[33] Glover, F., Tabu search fundamentals and uses (1995), University of Colorado: University of Colorado USA, Working paper
[34] Glover, F.; Kochenberger, G. A., Critical events tabu search for multidimensional knapsack problems, (Osman, I. H.; Kelly, J. P., Metaheuristics: The Theory and Appli cations (1995), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht), 407-428 · Zbl 0877.90055
[35] Glover, F.; Laguna, M., Tabu Search (1997), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht · Zbl 0930.90083
[36] Glover, F.; Lokkentangen, A., Solving zero-one mixed integer programming problems using tabu search (1994), University of Colorado: University of Colorado USA, updated version, by Lokketangen and Glover ( to appear in this issue).
[37] Glover, F.; Lokketangen, A., Tabu search for zero-one mixed integer programming with advanced level strategies and learning (1995), University of Colorado Boulder: University of Colorado Boulder USA, (forthcoming in International Journal of Operations and Quantitative Management)
[38] Goldberg, D., Genetic Algorithms in Search, Optimization and Machine Learning (1989), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0721.68056
[39] Grolimund, S.; Ganascia, J. G., Integrating case-based reasoning and tabu search for solving optimization problems, (Proceedings of the International Conference on Case-Base Reasoning. Proceedings of the International Conference on Case-Base Reasoning, Lectures Notes in Computer Science (1995), Springer: Springer Berlin)
[40] Hanafi, S., Contribution a la Resolution de Poblèmes Duaux de Grande Taille, (Thése Doctorat (1993), University de Valenciennes: University de Valenciennes France)
[41] Hanafi, S.; Fréville, A.; El Abdellaoui, A., Comparison of heuristics for the 0-1 multidimensional knapsack problem, (Osman, I. H.; Kelly, J. P., Metaheuristics: Theory and Applications (1995), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht), 449-466 · Zbl 0877.90056
[42] Hansen, P., The steepest ascent, mildest descent heuristic for combinatorial programming, (Congress on Numerical Methods in Combinatorial Optimization. Congress on Numerical Methods in Combinatorial Optimization, Capri, Italy (1986))
[43] Holland, J. H., Adaptation in Natural and Artificial Systems, An Introduction Analysis with Applications to Biology Control and Artificial Intelligence (1975), University of Michigan Press: University of Michigan Press Ann Arbor · Zbl 0317.68006
[44] Hopfield, J. J.; Tank, D. W., Neutral computation of decisions in optimization problems, Biological Cybernetics, 52, 141-152 (1985) · Zbl 0572.68041
[45] Kirkpatrick, S.; Gelatt, C. D.; Vechi, M. P., Optimization by simulated annealing, Science, 220, 671-680 (1983) · Zbl 1225.90162
[46] Lee, J. S.; Guignard, M., An approximate algorithm for multidimensional zero-one knapsack problems — A parametric approach, Management Sciences, 34, 402-410 (1988) · Zbl 0638.90069
[47] Lokketangen, A.; Glover, F., Probabilistic move selection in tabu search for zero-one mixed integer programming problems, (Osman, I. H.; Kelly, J. P., Metaheuristics: Theory and Applications (1995), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht), 467-488 · Zbl 0877.90058
[48] Lokketangen, A.; Jörnsten, K.; Storoy, S., Tabu search within a pivot and complement framework, International Transactions of Operations Research, 1, 305-316 (1994) · Zbl 0854.90102
[49] Lorie, J.; Savage, L. J., Three problems in capital rationing, Journal of Business, 28, 229-239 (1955)
[50] Metropolis, N.; Rosenbluth, A.; Rosenbluth, M.; Teller, A.; Teller, E., Equation of state calculations by fast computing machines, Journal of Chemical Physics, 21, 1087-1091 (1953) · Zbl 1431.65006
[51] Ohlssen, M.; Peterson, C.; Soderberg, B., Neural networks for optimization problems with inequality constraints: the knapsack problem, Neural Computation, 5, 331-339 (1993)
[52] Osman, I. H.; Kelly, J. P., Meta-heuristics: an overview, (Osman, I. H.; Kelly, J. P., Metaheuristics: Theory and Applications (1995), Kluwer Academic Publisher: Kluwer Academic Publisher Dordrecht), 1-22 · Zbl 0877.90065
[53] Petersen, C. C., Computational experience with variants of the Balas algorithm applied to the selection of R&D projects, Management Science, 13/9, 736-750 (1967)
[54] Senju, S.; Toyoda, Y., An approach to linear programming with 0-1 variables, Management Sciences, 15B, 196-207 (1968)
[55] Shih, W., A branch and bound method for the multiconstraint zero-one knapsack problems, Journal of Operations Research Society, 30, 369-378 (1979) · Zbl 0411.90050
[56] Straszak, A.; Libura, M.; Sikorski, J.; Wagner, D., Computer-assisted constrained approval voting, Group Decision and Negociation, 2, 375-385 (1993)
[57] Thiel, J.; Voβ, S., Solving multiconstraint zero-one knapsack problems with genetic algorithms (1992), TH Darmstadt: TH Darmstadt Germany, Working paper
[58] Toulouse, M.; Crainic, T. G.; Gendreau, M., Communication issues in designing cooperative multi-thread parallel searches (1995), Centre de recherche sur less Transports, University de Montreal, Working paper · Zbl 0877.90067
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.