Tabu search: global intensification using dynamic programming

Tabu search has proven highly successful in solving hard combinatorial optimization problems. In this paper, a hybrid method is proposed that combines adaptive memory, sparse dynamic programming, and reduction techniques to reduce and explore the search space. The 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. This 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. The new 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, the new 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.