Adaptive Scoring-and-Memory Policies for Repair Intensification in the Multi-Demand Multidimensional Knapsack Problem: A Comparative Analysis of Solution Quality and Trajectory Diversity

Abstract

The Multi-Demand Multidimensional Knapsack Problem (MDMKP) combines upper-bound capacities and lower-bound demands, producing a restrictive feasible region. We study three swap-based repair-intensification policies in a common hybrid framework: lightweight Hash tabu search, randomly sampled tabu search, and online learning-guided tabu search. The learning-guided policy uses a linear model updated during the run to score candidate swaps, while convergence, path diversity, quality–diversity maps, and PCA describe search behavior. On the 250M benchmark group, the complete ML policy attains a mean average gap of 0.76%, compared with 1.30% for Sampled and 1.65% for Hash, at higher computational cost. On the more constrained 100G group, its mean average gap is 1.23%, versus 13.84% and 14.17%, respectively. Non-parametric tests support the quality differences. Because the logical tabu memories differ, these results compare complete policies and do not isolate the effect of learning. A 165-run sensitivity screen finds no significant single-factor dependence within the tested ranges; Hash exponents and the learning score weight are the most responsive factors. The behavioral experiments do not isolate a causal benefit of diversity; they show that high recorded diversity alone is insufficient and suggest that selective intensification can be more important than broad trajectory dispersion. Future work will examine equal-memory ablations, controlled diversity interventions, dynamic penalties, balanced positive/negative online updates, and broader benchmarks.