  The multidimensional knapsack problem (MKP) is an NP-hard combinatorial
optimization problem whose solution is determining a subset of maximum total
profit items that do not violate capacity constraints. Due to its hardness,
large-scale MKP instances are usually a target for metaheuristics, a context in
which effective feasibility maintenance strategies are crucial. In 1998, Chu
and Beasley proposed an effective heuristic repair that is still relevant for
recent metaheuristics. However, due to its deterministic nature, the diversity
of solutions such heuristic provides is insufficient for long runs. As a
result, the search for new solutions ceases after a while. This paper proposes
an efficiency-based randomization strategy for the heuristic repair that
increases the variability of the repaired solutions without deteriorating
quality and improves the overall results.
