Critical Event Tabu Search for Multidimensional Knapsack Problems

We report a new approach to creating a tabu search method whose underlying memory mechanisms are organized around “critical events.” A balance between intensification and diversification is accomplished by a strategic oscillation process that navigates both sides of the feasibility boundary, and serves to define the critical events. Surrogate constraint analysis is applied to derive choice rules for the method. Computational tests show the approach performs more effectively than previous heuristics for multidimensional knapsack problems, obtaining optimal solutions for all problems in a standard testbed.