Tabu search: global intensification using dynamic programming

• Autorzy: Wilbaut C. , Hanafi S. , Fréville A. , Balev S.
• Języki publikacji: EN

Abstrakty

EN

Tabu search has proven highly successful in solving hard combinatorial optimization problems. In this paper, we propose a hybrid method that combines adaptive memory, sparse dynamic programming, and reduction techniques to reduce and explore the search space. Our approach starts with a bi-partition of the variables, involving a small core problem, which never exceeds 15 variables, solved using the "forward" phase of the dynamic programming procedure. Then, the remaining subspace is explored using tabu search, and each partial solution is completed with the information stored during the forward phase of dynamic programming. Our approach can be seen as a global intensification mechanism, since at each iteration, the move evaluations involve solving a reduced problem implicitly. The proposed specialized tabu search approach was tested in the context of the multidimensional 0-1 knapsack problem. Our approach was compared to ILOG's commercial product CPLEX and to the corresponding "pure" tabu search (i.e., without a core problem) for various sets of test problems available in OR-libraries. The results are encouraging. In particular, this enhances the robustness of the approach, given that it performs better than the corresponding pure tabu search most of the time. Moreover, our approach compares well with CPLEX when the number of variables is large; it is able to provide elite feasible solutions in a very reasonable amount of computational time.

Słowa kluczowe

EN

tabu search; dynamic programming; global intensification; multidimensional 0-1 knapsack problem

PL

programowanie dynamiczne

• Wydawca: Systems Research Institute, Polish Academy of Sciences
• Czasopismo: Control and Cybernetics
• Rocznik: 2006
• Tom: Vol. 35, no 3
• Strony: 579--598
• Opis fizyczny: Bibliogr. 25 poz.

Twórcy

autor

Wilbaut C.

autor

Hanafi S.

autor

Fréville A.

autor

Balev S.

• LAMIH-ROI, Universite de Valenciennes Le Mont Houy, 59313 Valenciennes, Cedex 9, France,

Bibliografia

• ANDONOV, R. BALEV, S. FREVILLE, A. and YANEV, N. (2001) A dynamic programming based reduction procedure for the multidimensional 0-1 knapsack problem. FRANCORO 2001, Quebec, submitted to European Journal of Operational Research.
• BELLMAN, R. (1957) Dynamic Programming. Princeton University Press. Princeton.
• BERTSIMAS, D. and DEMIR, R. (2002) An Approximate Dynamic Programming Approach to Multidimensional Knapsack Problems. Management Science 48, 550-565.
• CHU, P. and BEASLEY, J. (1998) A genetic algorithm for the multidimensional knapsack problem. Journal of Heuristics 4, 63-86.
• FRÉVILLE, A. (2004) The multidimensional 0-1 knapsack problem: An overview. European Journal of Operational Research 155 (1), 1-21.
• FRÉVILLE, A. and HANAFI, S. (2005) The multidimensional 0-1 knapsack problem - Bounds and computational aspects. IN: M. Guignard and K. Spielberg, eds., Advances in Operations Research. Annals of Operations Research, 139(1), 195-197.
• FRÉVILLE, A. and PLATEAU, G. (1990) Hard 0-1 multiknapsack test problems for size reduction methods. Investigacion Operativa 1, 251-270.
• FRÉVILLE, A. and PLATEAU, G. (1994) An efficient preprocessing procedure for the multidimensional 0-1 knapsack problem. Discrete Applied Mathematics 2 (2), 147-167.
• FRÉVILLE, A. and PLATEAU, G. (1996) The 0-1 bidimensional knapsack problem: towards an efficient high-level primitive tool. Journal of Heuristics 2, 147-167.
• GLOVER, F. (1986) Future paths for integer programming and links to artificial intelligence. Computers and Operations Research 19, 533 549.
• GLOVER, F. (1989) Tabu Search-Part I. ORSA Journal on Computing 1 (3). 190-206.
• GLOVER, F. (1990) Tabu Search-Part II. ORSA Journal on Computing 2 (1), 4-32.
• GLOVER, F. and KOCHENBERGER, G. (1996) Critical event tabu search for multidimensional knapsack problems. In: Meta-Heuristics: Theory and Applications. Kluwer Academic Publishers, 407-427.
• GLOVER, F. and LACUNA. M.(1997) Tabu Search. Kluwer Academic Publishers, Dordrecht.
• HANAFI, S. and FRÉVILLE, A. (1998) An efficient tabu search approach for 0-1 multidimensional knapsack problem. European Journal of Operational Research 106, 659-675.
• HANSEN, P. (1986) The steepest ascent mildest descent heuristic for combinatorial programming, Congress on Numerical Methods in Combinatorial Optimization. Capri, Italy.
• KELLERER, H. PFERSCHY, U. and PISINGER, D. (2004) Knapsack Problems. Springer.
• MARTELLO, S. and TOTH, P. (1990) Knapsack Problems: Algorithms and Computer Implementations. Series in Discrete Mathematics and Optimization. Wiley Interscience.
• OSORIO, M.A. GLOVER, F. and HAMMER, P. (2002) Cutting and Surrogate Constraint Analysis for Improved Multidimensional Knapsack Solutions. Annals of Operational Research 117. 71-93.
• PLATEAU, G. and ELKIHEL, M. (1985) A hybrid method for the 0-1 knapsack problem. Methods of Operations Research 49, 277 293.
• SAVELSBERG, M.W.P. (1994) Preprocessing and probing techniques for mixed integer programming problems. ORSA Journal of Computing 6, 445-454.
• SOYSTER, A.L. LEV, B. and SLIVKA, W. (1978) Zero-one programming with many variables and few constraints. European Journal of Operational Research 2, 195-201.
• TOTH, P. (1980) Dynamic programming algorithms for the zero-one knapsack problem. Computing 25, 29-45.
• VASQUEZ, M. and HAO, J.K. (2001) Une approche hybride pour le sac à dos multidimensionnel en variables 0-1. RAIRO Operations Research 35, 415-438.
• VIADER, F. (1998) Methodes de Programmation Dynamique et de Recherche Arborescente pour l’Optimisation Combinatoire: Utilisation Conjointe des deux approches et Parallélisation d'Algorithmes. Ph.D. Thesis, Universite Paul Sabatier, Toulouse, France.